题解：P9835 [USACO05OPEN] Landscaping G

· · 题解

1. 思维 + 树形 dp 题。

2. 题意：

左边为单调不下降，右边为单调不上升的部分为山顶，可以任意移走土块，但显然是一个一个山顶去移走，求最多留下 k 个山顶时的最小移走土数。

3. 思路：

提供一种加强版 n 为 10^5 也能过的方法。

时间复杂度为 O( n \times k^2 )。

做法不难，但细节较多。 先将山分为多块，也是矩阵，划分方法如下图。

即将一个山顶划分为不同层的矩阵，

然后对矩阵建立从属关系，及左右边界是否包含。

下图黑字为编号，蓝字为块大小。

再利用块大小做一个树形 dp，具体转移如下，有具体解释。

4. 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define M 26
#define inf 1000000000000007
ll n,m,u,v,ans=inf,f[N][M],p; 
ll a[N],b[N],cnt;
ll q[N],qq[N],cnt1=1;
ll t[N],cnt2;
//f[i][j]为编号为i的块及其子树内 有j个山顶的 最小移走土数 
//a为该块大小  b为该块最左点下标  cnt为对应的块数
//q，qq为队列  cnt1为对应队内数  q为高度，是单调序列  qq为对应的最左点 
//t为可能为从属块队列，单调递增，且无包含关系  cnt2为对应队内数  
vector<ll>s[N];//记录块从属关系 
void dfs(ll x,ll y) {//树形dp 
    if(!s[x].size()) f[x][1]=0;//若x为叶子结点，则其自身为山顶 
    for(auto i:s[x]) if(i!=y) {
            dfs(i,x);
            a[x]+=a[i];//算x子树大小 
            for(ll j=m; j>=0; j--) {//按从大到小，先更新留下山顶多的 
                for(ll k=m-j; k>=1; k--) f[x][j+k]=min(f[x][j+k],f[x][j]+f[i][k]);//i的山顶移走k个，x内共j+k个山顶 
                f[x][j]+=f[i][0];//i的山顶全部移走 
            }
        }
    f[x][0]=a[x];//x全移走 
    return;
}
int main() {
    scanf("%lld%lld%lld",&n,&m,&u);
    q[cnt1]=u;
    qq[cnt1]=1;
    for(ll i=2; i<=n; i++) {
        scanf("%lld",&u),p=i;
        while(1) {
            if(q[cnt1]<=u) break;//山顶左侧必为单调不下降增
            p=qq[cnt1];
            v=q[cnt1]-u;
            if(cnt1>1) v=min(v,q[cnt1]-q[cnt1-1]);
            ++cnt;
            a[cnt]=v*(i-qq[cnt1]);//计算块大小 
            b[cnt]=qq[cnt1];//块的最左点 
            while(cnt2&&b[cnt]<=b[t[cnt2]]) s[cnt].push_back(t[cnt2]),cnt2--;// 连接从属块，记得删掉被连了的 
            ++cnt2;
            t[cnt2]=cnt;
            cnt1--;
        }
        if(q[cnt1]<u) ++cnt1,q[cnt1]=u,qq[cnt1]=p;//同高度不必多加入队列，因为前面的更左 
    }
    u=q[cnt1];
    while(cnt1) {//同上可得 
        ++cnt;
        a[cnt]=(n+1-qq[cnt1])*(u-q[cnt1-1]);
        b[cnt]=qq[cnt1];
        u=q[cnt1-1];//更新高度 
        while(cnt2&&b[cnt]<=b[t[cnt2]]) s[cnt].push_back(t[cnt2]),cnt2--;
        ++cnt2;
        t[cnt2]=cnt;
        cnt1--;
    }
    for(ll i=1; i<=cnt; i++) for(ll j=1; j<=m; j++) f[i][j]=inf;//初始化，j必须从1开始 
    dfs(cnt,0);
    for(ll i=1; i<=m; i++) ans=min(ans,f[cnt][i]);//不一定有m个山顶 
    printf("%lld",ans);
    return 0;
}