力扣天池赛-221021天池-04. 意外惊喜(分治优化dp)

1.考虑用倍增优化背包？（预处理以i为起点，长度为1、2、4…的背包的答案）

不太行，实际两个背包合并的复杂度是O(1000*1000)的，不如背包内放一个物品的复杂度O(1000)

2.考虑用背包撤销？（把物品放进去，撤销的时候做一遍逆操作）

不太行，max信息无法撤销，sum这种各个贡献独立的才可撤销

3.考虑用分治优化背包，设当前区间[l,r]，

先用tmp数组把当前dp暂存下来，把[mid+1,r]的01背包算进去后，再递归进[l,mid]

用tmp数组将dp恢复，把[l,mid]的01背包算进去后，再递归进[mid+1,r]

在进入一个区间之前，这个区间的补集已经在之前的递归中算过了，

在递归每一层的区间时，算区间的另一半背包的答案，

当l=r的时候，即枚举当前背包是那个不全取的背包，更新答案

代码

class Solution {
public:
    int ans,up,a[2005],sz[2005],dp[1005];
    void dfs(vectorint>>& p,int l,int r){
        if(l==r){
            ans=max(ans,dp[up]);
            int cur=0;
            for(int i=1;i<=min(up,sz[l]);++i){
                cur+=p[l][i-1];
                ans=max(ans,dp[up-i]+cur);
            }
            return;
        }
        int mid=(l+r)/2;
        vector<int>tmp(1005,0);
        for(int i=0;i<=up;++i){
            tmp[i]=dp[i];
        }
        for(int i=mid+1;i<=r;++i){
            for(int j=up;j>=sz[i];--j){
                dp[j]=max(dp[j],dp[j-sz[i]]+a[i]);
            }
        }
        dfs(p,l,mid);
        for(int i=0;i<=up;++i){
            dp[i]=tmp[i];
        }
        for(int i=l;i<=mid;++i){
            for(int j=up;j>=sz[i];--j){
                dp[j]=max(dp[j],dp[j-sz[i]]+a[i]);
            }
        }
        dfs(p,mid+1,r);
    }
    int brilliantSurprise(vectorint>>& p, int lim) {
        ans=0;
        up=lim;
        int n=p.size();
        for(int i=0;i
            a[i]=accumulate(p[i].begin(),p[i].end(),0);
            sz[i]=p[i].size();
        }
        memset(dp,0,sizeof dp);
        dfs(p,0,n-1);
        return ans;
    }
};