hdu 5534 Partial Tree

http://acm.hdu.edu.cn/showproblem.php?pid=5534

说好的区域赛保个铜就好了，但赛后发现我们离银真的只差一点的时候真的感觉非常遗憾。

尤其是队里唯一负责dp的某人...窝→_→

这个水dp赛后分分钟AC啊，然而比赛时窝就是没过。

没过就是没过，没什么借口可找。

题目做法就是利用树的性质，每个点都至少有一度，所有点度数和为2*（n-1)，很容易想出n^3方做法，度数和与点数各开一维，然后o(n)转移

其实我们可以给每个点预先分配一度，然后用其他的度数来替换一度。这样将除一度外的所有度的价值改为w[i]-w[1],度数的贡献改为i-1，跑一次完全背包就能得到答案惹，时间复杂度降为n^2

#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("
");
		printf("%d
",dp[len]);
	}
	return 0;
}