动归.
注: 我发现ural的时间限制很宽裕但空间限制很BT...所以总是有Crash的现象...
#include<iostream> using namespace std; int W[30],n,tot,temp; bool T[5000001]; int main() { int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&W[i]); tot+=W[i]; } temp=tot/2; memset(T,false,sizeof(T)); T[0]=true; for(i=1;i<=n;i++) { for(j=tot;j>=W[i];j--) { if(T[j-W[i]]) T[j]=true; } } for(i=temp;i>=0;i--) { if(T[i]) break; } printf("%d/n",tot-2*i); return 0; }
