hdu 5534 Partial Tree

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2020;
int dp[maxn<<1];
int w[maxn];
int main()
{
	int i,j,t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int sum=0;
		int len=(n-1)*2;
		for(i=1;i<n;i++)
			scanf("%d",&w[i]);
		memset(dp,0,sizeof(dp));
		len=len-n;
		dp[0]=n*w[1];
		for(i=2;i<n;i++)
		{
			for(j=0;j<=len;j++)
				if(j>=i-1)
					dp[j]=max(dp[j],dp[j-i+1]+w[i]-w[1]);
		}
	//	for(i=0;i<=len;i++)	printf("%d ",dp[i]);	printf("\n");
		printf("%d\n",dp[len]);
	}
	return 0;
}