可以修建的缆车总数不超过n，于是可以先通过$O(n^2)$的枚举求出所有可以修建的缆车。

对于一个缆车，若它仅连接i和i+1，那么它不受k的限制，把这种缆车额外取出，从大到小排序。

剩下的缆车两两之间要么是包含关系，要么没有任何交集，按照包含关系可以建出一棵树。

设f[i][j][k]表示以i为根的子树中修建了j个缆车，且该区间内所有点上面的缆车数的最大值为k的最优解。

则对于x的孩子i，通过枚举a,b,c,d，可以得到：

f'[x][a+c][max(b,d)]=max(f'[x][a+c][max(b,d)],f[x][a][b]+f[i][c][d])

可以通过讨论b和d的大小关系，维护两个前缀最大值来省去d的枚举。

如果把a的枚举上界定为x之前部分的子树大小，c的枚举上界定为i的子树大小，那么对于树上的两个点，只会在它们的lca处被DP到，所以这个树形DP的时间复杂度为$O(kn^2)$。

最后统计答案时，只要枚举修建的受k限制的缆车数和不受k限制的缆车数，取个最大值即可。

 

#include
     
      #include
      
       #define rep(i,l,n) for(int i=l;i<=n;i++)#define dep(i,n,l) for(int i=n;i>=l;i--)using namespace std;const int N=210,inf=~0U>>2;int T,n,m,i,j,k,flag,x[N],y[N],cnt,one,b[N],g[N],nxt[N],ans;int size[N],f[N][N][10],t[N][10];struct P{int l,r,w;P(){}P(int _l,int _r,int _w){l=_l,r=_r,w=_w;}}a[N];inline bool cmp(int x,int y){return x>y;}inline void up(int&a,int b){if(a
       
        =y[i]){flag=0;break;}      if(flag){        if(i+1==j){          b[++one]=x[j]-x[i];        }else{          a[++cnt]=P(i+1,j-1,x[j]-x[i]);        }      }    }    if(one>1)sort(b+1,b+one+1,cmp);    rep(i,2,one)b[i]+=b[i-1];    rep(i,1,cnt){      j=0;      rep(k,1,cnt)if(a[k].l
        
         a[i].r)if(!j||a[k].w