【BZOJ4254】Aerial Tramway
题意：给你一座山上n点的坐标，让你在山里建m条缆车，要求缆车两端的高度必须相等，且中间经过的点的高度都小于缆车的高度。并且不能存在一个点位于至少k条缆车的下方。求缆车的最大总长度。
n,m<=200,k<=10。
题解：这么神奇的题面居然有人能想到要用树形DP。。。
先枚举所有可能的缆车，然后暴力得出这些缆车的关系。因为上面的缆车一定比它下面的缆车长，所以这形成了一个树形结构，我们建树跑树形DP。
用f[x][a][b]表示x的子树中已经减了y个缆车，且一个点最多位于k条缆车下方，的最大总长度。转移时是惯用的树形背包套路，然后用前缀最大值优化一下即可。时间复杂度O(n*m*k)。
#include#include #include #include using namespace std;int T,n,m,K,tot,ans,cas;int x[210],y[210],v[210],bel[210],siz[210],g[210][15],f[210][210][15],d[210];vector ch[210];inline int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}void dfs(int x){ siz[x]=1; int i,j,k,l,y; for(l=0;l<=K;l++) f[x][0][l]=0; for(i=0;i<(int)ch[x].size();i++) { y=ch[x][i],dfs(y); memcpy(g,f[x],sizeof(f[x])); for(j=0;j<=siz[x]&&j<=m;j++) for(k=0;k<=siz[y]&&j+k<=m;k++) for(l=0;l<=K;l++) g[j+k][l]=max(g[j+k][l],f[x][j][l]+f[y][k][l]); siz[x]+=siz[y]; for(j=0;j<=siz[x]&&j<=m;j++) for(l=1;l<=K;l++) f[x][j][l]=max(g[j][l],f[x][j][l-1]); } for(j=min(m,siz[x]);j>=1;j--) for(l=1;l<=K;l++) { f[x][j][l]=max(f[x][j][l],f[x][j-1][l-1]+v[x]); f[x][j][l]=max(f[x][j][l],f[x][j][l-1]); } ans=max(ans,f[x][m][K]);}void work(){ tot=0,K--; int i,j; for(i=1;i<=n;i++) x[i]=rd(),y[i]=rd(),ch[i].clear(),bel[i]=0; for(i=1;i<=n;i++) { for(j=i-1;j>=1;j--) { if(y[j]>y[i]) break; if(y[j]==y[i]) { bel[i]=++tot,v[tot]=x[i]-x[j],d[tot]=0; break; } } if(y[j]==y[i]&&bel[i]) for(j++;j