2016 ICPC Hong Kong G Scaffolding —— 笛卡尔树上DP

本文主要是介绍2016 ICPC Hong Kong G Scaffolding —— 笛卡尔树上DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

他这个题意稍微的不正确，它应该是放了这个竹子之后就到这个竹子上面（也许）。否则样例，题解和程序就不对了吧。

题解：

大致思路就是这样，我这里用dp代替了f，res代替了g。
sum表示子树的值的和，siz表示子树大小。
ll v=(a[x]-a[fa])*siz[x]-res[ls[x]]-res[rs[x]];
表示当前点把统治的区间内的所有点的高拆到和父亲一样高的时候，还需要拆几个（因为要减去儿子的贡献）
res[x]=dp[x]*m-sum[x]+a[fa]*siz[x];
表示这个点可以拆多少个，减去这个点需要拆多少个就是它对上面的贡献

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
ll dp[N],res[N],sum[N],siz[N],a[N];
int fa[N],ls[N],rs[N],st[N],top;
int n;
ll m;
void build(){for(int i=1;i<=n;i++){int f=0;while(top&&a[st[top]]>a[i])top--,f=1;if(top)fa[i]=st[top],rs[st[top]]=i;if(f)ls[i]=st[top+1],fa[ls[i]]=i;st[++top]=i;}
}
void dfs(int x,int fa){if(!x)return ;dfs(ls[x],x),dfs(rs[x],x);dp[x]=dp[ls[x]]+dp[rs[x]];sum[x]=sum[ls[x]]+sum[rs[x]]+a[x];siz[x]=siz[ls[x]]+siz[rs[x]]+1;ll v=(a[x]-a[fa])*siz[x]-res[ls[x]]-res[rs[x]];if(v>0)dp[x]+=(v+m-1)/m;res[x]=dp[x]*m-sum[x]+a[fa]*siz[x];
}
int main()
{scanf("%d%lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build();dfs(st[1],0);printf("%lld\n",dp[st[1]]);return 0;
}

这篇关于2016 ICPC Hong Kong G Scaffolding —— 笛卡尔树上DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---