MayTheBestPetWin

#Dp

我们要求的是$max\{\sum S1’B-\sum S2’A, \sum S2’B-\sum S1’A \}$的最小值，很难直接DP，因为无法知道当前元素对答案的贡献，因为最终的答案是取$max$的，无法再过程中取得最优值，需要考虑每个元素对答案的贡献.

如果当前元素放到集合$S1$ ，其对左边和的贡献是$A$
如果当前元素放到集合$S2$ ，其对左边和的贡献是$-B$

因此当前元素对左边和的贡献来回相差$A+B$ ，其实
$$
\sum S1’B-\sum S2’A=\sum S1’B+\sum S2’B-(\sum S2’A+\sum S2’B)
$$
$$
=\sum B-\sum S2’(A+B)
$$
同理右边和即为
$$
\sum B-\sum S1’(A+B)=\sum B-(\sum(A+B)-\sum S2’(A+B))
$$
$$
= \sum S2’(A+B)-\sum A
$$
因此答案即为$max\{\sum B-\sum S2’(A+B) , \sum S2’(A+B)-\sum A\}$
直接Dp求出所有可行的$\sum S2’(A+B)$

class MayTheBestPetWin {
public:
    static const int M = 100*10000+5;
    bitset<M>cnt;
    void Chk(int &a,int b){
        if(a==-1||a>b)a=b;
    }
    int calc(vector <int> A, vector <int> B) {
        int n=A.size();
        cnt.set(0);
        for(int i=0;i<n;++i){
            cnt|=cnt<<(A[i]+B[i]);
        }
        int sumA=0,sumB=0,ans=-1;
        for(int i=0;i<n;++i)sumA+=A[i],sumB+=B[i];
        for(int i=0;i<M;++i){
            if(cnt[i])Chk(ans,max(abs(sumA-i),abs(sumB-i)));
        }
        return ans;
    }
};