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;
    }
};