题解：P1792 [国家集训队] 种树

Richard_Whr · 2024-09-10 21:46:02 · 题解

首先可以容易的写出一个背包，设 f_{i,j,0/1} 表示 i 选不选，选出 j 个的最大价值。

然后可以比较容易的转移。

众所周知，这玩意可以用费用流模型证出来凸性。

然后对于凸性背包 DP，可以采用序列分治 + 闵和合并背包的方式。

流程大概是：

我们发现分治后合并还有限制是交接处不能同时选。

因此设状态 F_{l,r,0/1,0/1} 表示 [l,r] 的背包，左右端点有没有选。

• 分治做出左右儿子的背包，对于叶子的初始化是简单的
• 然后合并两个凸性背包相当于对两个背包的差分数组做归并排序。

然后就没了，这个做法可以做出 m \in [1,n] 的所有答案，且是单 \log 的。

代码实现常数非常大，如果有高人可以给出常数更小更好写的代码，希望私信指教我。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,Inf=1e8;
typedef vector<int> Vec;
Vec F[N*2][2][2];
int w[N];
int idx;
int n,m;

Vec Max(Vec A,Vec B)
{
    if(!A.size()) return B;
    if(!B.size()) return A;
    Vec res;
    res.resize(max(A.size(),B.size()));
    for(int i=1;i<A.size();i++) A[i]+=A[i-1];
    for(int i=1;i<B.size();i++) B[i]+=B[i-1];
    for(int i=0;i<res.size();i++)
    {
        res[i]=-Inf;
        if(i<A.size()) res[i]=max(res[i],A[i]);
        if(i<B.size()) res[i]=max(res[i],B[i]);
    } 
    for(int i=res.size()-1;i>=1;i--) res[i]=res[i]-res[i-1];
    return res;
}

Vec merge(Vec A,Vec B)
{
    vector<int> res;
    res.resize(A.size()+B.size());
    merge(A.begin(),A.end(),B.begin(),B.end(),res.begin(),greater<int>());
    return res;
}

int solve(int l,int r)
{
    int u=++idx;
    if(l==r)
    {
        F[u][1][1].push_back(w[l]);
        return u;
    }
    int mid=l+r>>1;
    int ls=solve(l,mid),rs=solve(mid+1,r);
    for(int a=0;a<2;a++)
    {
        for(int b=0;b<2;b++)
        {
            for(int c=0;c<2;c++)
            {
                for(int d=0;c+d<2;d++)
                {
                    F[u][a][b]=Max(F[u][a][b],merge(F[ls][a][c],F[rs][d][b]));
                }
            }
        }
    }
    return u;
}


signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];

    int rt=solve(1,n);
    vector<int> res;

    for(int a=0;a<2;a++)
    {
        for(int b=0;a+b<2;b++)
        {
            res=Max(res,F[rt][a][b]);
        }
    }

    for(int i=1;i<res.size();i++) res[i]+=res[i-1];

    int ans=0;
    if(res.size()<m) cout<<"Error!\n",exit(0);
    cout<<res[m-1]<<"\n";


    return 0;
}