HDU 1171 Big Event in HDU [多重背包] 分手后的思念是犯贱 2022-05-29 10:24 116阅读 0赞 #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; int ttt[5005]; int dp[255555]; int main(int argc, char *argv[]) { int n,a,b; int sum,i,j,k; while(scanf("%d",&n)!=EOF&&n>0) { k=0; sum=0; memset(dp,0,sizeof(dp)); memset(ttt,0,sizeof(ttt)); for(i=0;i<n;i++) { scanf("%d %d",&a,&b); sum+=a*b; while(b--) { ttt[k++]=a; } } for(i=0;i<k;i++) { for(j=sum/2;j>=ttt[i];j--) dp[j]=max(dp[j],dp[j-ttt[i]]+ttt[i]); } printf("%d %d\n",sum-dp[sum/2],dp[sum/2]); } return 0; }
还没有评论，来说两句吧...