题目链接 题意是有n个点，需要加边把他们连接成一棵树，然后每个点的点权的其度数对应的价值。然后问能够连接形成的树的最大权值。 抽象出来其实就是有n-1个物品，背包大小为 2*(n-1), 然后每个物品可以取多次，但是必须取出恰好n个东西出来，因为对应n个点。朴素的解法是我们直接多加一维状态去表示，但是很麻烦的是三维的dp显然没办法在这个题里面做。 有一个精妙的操作可以把三维优化成二维，就是在初始的状态下，我们先给每个点一个度，然后从度数为2的点开始枚举，这时背包的大小变成了2*(n-1) - n = n-2 ，然后方程的转移dp[i][j] = max(dp[i-1][j] , dp[i][j-(i-1)]+f[i] - f[1]) 。这个地方非常的精妙，因为我们当前枚举到i，实际上由于已经放入了一个度数为1的点，所以这个i的实际代价只有(i-1)，然后用其本身的价值减去已经放入的度数为1的价值，即是答案。
#include<cmath> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const LONG INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, n , 1 int f[2100] ; int dp[2200] ; int main() { int T; cin >>T; while(T--) { int n ; cin >> n ; clr2(dp) ; for(int i= 1; i< n ; ++ i) scanf("%d",&f[i]) ; dp[0] = n*f[1] ; for(int i = 2;i< n; ++i) for(int j = 0 ; j<=n-2 ; ++j) if(j>=i-1)dp[j] = max(dp[j] , dp[j-(i-1)] + f[i]-f[1]) ; cout<<dp[n-2]<<endl; } }