[数据结构与算法]Leetcode天池大赛压轴题分治dp

LeetCode天池大赛第四题

根据题意，有一个重要结论，就是很多数组，我要么不拿，要么拿完
至多只剩下一个未拿完的序列

枚举每个序列作为结束序列，也就是未拿完序列
如果直接01背包将会是n方级别
那么能不能撤销呢？不行，因为这里的运算是max，做不到撤销
考虑重复运算了哪些东东，01背包贡献完的dp数组重复太多次了
用分治去写，先初始化一个全局dp数组
dfs(L,R)表示dp数组已经运算完其他区间，现在要考虑L，R内的情况
对于一个区间L，R
t=dp
如果L，mid先贡献完dp，然后递归右边dfs(mid+1,R)
还原现场dp=t
现在mid+1,R对dp数组做出贡献，然后递归左边dfs(L,mid)

结束–L==R
此时dp数组表示该序列以外的运算结果
现在要对该序列进行更新
最大化全局ans

class Solution {
    typedef vector<int> vi;
    static const int N=2020;
    // vector<vi> dp=vector<vi>(N,vi(0));
    vector<vi> P;
    vi sum=vi(N,0);
    vi dp=vi(N,0);
    int ans,m;
public:
    void dfs(int l,int r){
        if(l==r){
            int s=0;
            for(int i=1;i<=P[l].size();i++){
                if(i>m)break;
                s+=P[l][i-1];
                dp[m]=max(dp[m],dp[m-i]+s);
            }
            ans=max(ans,dp[m]);
            return;
        }
        int mid=l+r>>1;
        auto t=dp;
        //计算左边01背包
        for(int i=l;i<=mid;i++){
            for(int j=m;j>=P[i].size();j--){
                dp[j]=max(dp[j],dp[j-P[i].size()]+sum[i]);
            }
        }
        //计算完01背包给右边递归用
        dfs(mid+1,r);
        
        //dp是个全局数组，定义是[L,R]以外的01背包的贡献，现在要计算区间内的贡献
        dp=t;
        //计算右边01背包
        for(int i=mid+1;i<=r;i++){
            for(int j=m;j>=P[i].size();j--){
                dp[j]=max(dp[j],dp[j-P[i].size()]+sum[i]);
            }
        }
        //计算完01背包给左边递归用
        dfs(l,mid);
    }
    int brilliantSurprise(vector<vector<int>>& p, int limit) {
        m=limit;
        P=p;
        for(int i=0;i<p.size();i++){
            for(int j=0;j<p[i].size();j++){
                sum[i]+=p[i][j];
            }
        }
        dfs(0,p.size()-1);
        return ans;
    }
};

第三题，带有限制的单调栈

class Solution {
public:
    vector<int> arrangeBookshelf(vector<int>& order, int limit) {
        auto a=order;
        int n=a.size();
        map<int,int>sum,del,in;
        //如果你比我小而且（ans里面的cnt+i后面的cnt）>limit，可以删
        // 而且你加进来后in【a[i]】不能大于limit
        for(auto x:a)sum[x]++;
        vector<int>ans;
        for(int i=0;i<n;i++){
            sum[a[i]]--;
            while(ans.size()&&ans.back()>a[i]&&in[ans.back()]+sum[ans.back()]>limit&&in[a[i]]+1<=limit){
                in[ans.back()]--;
                ans.pop_back();
            }
            ans.push_back(a[i]);
            in[a[i]]++;
            while(ans.size()&&in[ans.back()]>limit){
                in[ans.back()]--;
                ans.pop_back();
            }
        }
        return ans;
    }
};