题目地址：HDU 1171
还是水题。。普通的01背包。注意数组要开大点啊。。。。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; int dp[260000], v[600], k[600], c[260000]; int main() { int n, i, j, y, z, sum, s, cnt, x; while(scanf("%d",&n)!=EOF) { if(n<0) break; sum=0; for(i=0;i =0) { c[cnt++]=y*v[i]; x-=y; y*=2; } if(x) c[cnt++]=x*v[i]; } s=sum; sum/=2; dp[0]=1; for(i=0;i =c[i];j--) { if(dp[j-c[i]]) dp[j]=1; } } int ans; for(i=sum;i>=0;i--) { if(dp[i]) { ans=i; break; } } printf("%d %d\n",s-ans,ans); } return 0; }