思路:总度数为2n-2,由于每个节点都至少要有1个度,所以可以看做把剩余n-2个点放入n个节点的背包问题。dp[i]表示放入i个度后的最大值
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int INF=-1e9; int f[10010]; int dp[10010]; int main() { int T; scanf("%d",&T); while(T--) { int n; memset(dp,INF,sizeof(dp)); scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d",&f[i]); dp[0]=n*f[1]; for(int i=1;i<=n-2;i++) { for(int j=i;j<=n-2;j++) { dp[j]=max(dp[j],dp[j-i]+f[i+1]-f[1]);//放入后度数为i+1 } } printf("%d ",dp[n-2]); } return 0; }