首页 > 代码库 > HDU 1171 Big event in hdu

HDU 1171 Big event in hdu

2024-07-16 04:31:18   238人阅读

这题 就是 简单的 多重背包应用..本来以为可以很快地写出来;

WA了无数次就是没找出哪里错了(有太自信的缘故);

百度了半天别人的代码,对照了半小时...说实话都要吐血了....;

终于发现了哪里错了;

教训,教训啊;再简单的题目也要慢慢来,不能太自信;

 1 #include<iostream> 2 #define maxn 2000000 3 int v[1005],c[1005],dp[maxn]; 4 #define max(a,b) (a>b?a:b) 5 using namespace std; 6 int main() 7 { 8     //freopen("1171.txt","r",stdin); 9     int n,i,j,sum;10     while(~scanf("%d",&n))11     {12         memset(v,0,sizeof(v));13         memset(c,0,sizeof(c));14         sum=0;15         if(n<=0) break;16         for(i=1;i<=n;i++)17         {18             scanf("%d%d",v+i,c+i);19             sum+=v[i]*c[i];20         }21         memset(dp,0,sizeof(dp));22         int value=http://www.mamicode.com/sum/2;23         for(i=1;i<=n;i++)24         {25             if(v[i]*c[i]>=value)26             {27                 for(j=v[i];j<=value;j++)28                     dp[j]=max(dp[j],dp[j-v[i]]+v[i]);29                 continue;30             }31             int k=1;32             while(k<c[i])33             {34                 for(j=value;j>=v[i]*k;j--)35                     dp[j]=max(dp[j],dp[j-k*v[i]]+k*v[i]);36                 c[i]-=k;37                 k+=k;38             }39             for(j=value;j>=v[i]*c[i];j--)40                 dp[j]=max(dp[j],dp[j-c[i]*v[i]]+v[i]*c[i]);41         }42         43         printf("%d %d\n",sum-dp[value],dp[value]);44     }45     return 0;46 }

 


联系
我们