【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 <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
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<int> 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<i;j++) if(y[j]<y[i]&&bel[j]&&!d[bel[j]])d[bel[j]]=1,ch[bel[i]].push_back(bel[j]);}memset(f,0xc0,sizeof(f));v[++tot]=-1<<20;for(i=1;i<tot;i++) if(!d[i]) ch[tot].push_back(i);ans=-1,dfs(tot);printf("%d\n",ans);
}
int main()
{while(scanf("%d%d%d",&n,&m,&K)!=EOF){printf("Case %d: ",++cas);work();}return 0;
}//14 3 3 1 8 2 6 3 4 4 6 5 3 6 4 7 1 8 4 9 6 10 4 11 6 12 5 13 6 14 8 14 3 2 1 8 2 6 3 4 4 6 5 3 6 4 7 1 8 4 9 6 10 4 11 6 12 5 13 6 14 8 ?
)
