题目描述
仗助、亿太、胖重分赃不均闹起来了。
仗助和亿太拿着n张面值分别为a[i]的钞票决定均分，他们希望把钞票分成金额相等的两份，且未分配的剩余钞票总金额最小。
对于剩余的部分，则用替身能力复制成两倍再均分（大雾）。
求他们最终各自能带回家的金额。
题解
我们思考DPDPDP，傻逼DPDPDP就是f[i][j][k]f[i][j][k]f[i][j][k]表示jjj,kkk的最小差值，然而我们其实并不关心jjj,kkk的具体值。
我们要有坚定不移的精神，看什么恶心就把什么拿到维度里面去维护
记f[i][j]f[i][j]f[i][j]的jjj为差值为jjj时的最大值，那么答案就是sum−f[n][0]/2sum-f[n][0]/2sum−f[n][0]/2，其次我们的差值并没有分是A和B还是B和A，所以我们转移的时候加个abs
代码
#include <bits/stdc++.h>#define maxn 200005#define INF 0x3f3f3f3fusing namespace std;int n,a[maxn],tax[maxn],mx,sum;int f[2][maxn],pos=1;int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i],mx=max(mx,a[i]);memset(f[0],0x8f,sizeof f[0]);memset(f[1],0x8f,sizeof f[1]); f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=mx;j++){f[pos][j]=max(f[pos^1][j],max(f[pos^1][abs(j-a[i])],f[pos^1][j+a[i]])+a[i]);}pos^=1;}cout<<sum-f[pos^1][0]/2<<endl;return 0;}
