包RE做法
原题链接：27924.瓜分天下
2024-08-19 14:53:50
发布于：广东
16阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> a(n+1);
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int cnt=sum/2;
vector<int> dp(sum*1000000000000000000000000+1);//dp[i]表示判断完第i个城池 能够获得的最大资源度
for(int i=1;i<=n;i++){
for(int j=cnt;j>=a[i];j--){
//在j资源度的情况下，选择这个城池 还是 不选择
dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
}
}
int k=dp[cnt];
int u=sum-k;
cout<< u-k;
return 0;
}
这里空空如也
有帮助，赞一个