PKU 2576 Tug of War
http://poj.org/problem?id=2576
n個の数字を、n/2個とn-n/2個のグループに分ける。
両方のグループの数字の和が出来るだけ近くなるようなわけ方にしたときに、両方の数字の和を求めろというような問題。
他の人の実行タイムを見る限りオーダーを少し落とせるようなのですが、ちょっとやり方がよくわからないので、こんな感じで解きました。
適当にググッて調べたいと思います。
bool dp[111][55001]; int in[100]; main(){ int n; cin>>n; int sum=0; rep(i,n){ cin>>in[i]; sum+=in[i]; } dp[0][0]=true; rep(i,n){ for(int u=n-1;u>=0;--u){ rep(nu,sum+1)if(dp[u][nu])dp[u+1][nu+in[i]]=true; } } int a=0,b=sum; rep(i,sum){ if(!dp[n/2][i])continue; if(abs(b-a)>abs(sum-2*i)){ a=i; b=sum-i; } } cout<<min(a,b)<<' '<<max(a,b)<<endl; }