BZOJ4247: 挂饰 dp

题解：

首先注意到假如目前的树上能够插入$n$个节点，那么插入一个能够插入$m$个节点的节点，无论这个节点接在原来的一个位置上，还是这个节点成为新的树的根节点，这棵树都能够插入$n+m-1$个节点。

也就是说，树的形态我们并不需要考虑，只需要考虑这棵树能够插入多少节点。

我们考虑令$f[i][j]$表示前$i$种物品形成的树，树中能够插入$j$个节点的最大价值。

显然利用背包就可以做了。

我加了一点优化：对于$m=0$的节点最后一起贪心的考虑。

虽然复杂度依然是$O(n^2)$，但是我跑得很快目前是rank1。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 2010
int f[2][N];

int a[N],b[N],c[N];

inline void maxi(int&x,int y){
	if(x<y)
		x=y;
}
inline bool cmp(const int&a,const int&b){
	return a>b;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n;
	scanf("%d",&n);
	int n1=0,n2=0,i,j,_a,_b;
	for(i=1;i<=n;++i){
		scanf("%d%d",&_a,&_b);
		if(_a==0)
			c[++n2]=_b;
		else{
			a[++n1]=_a;
			b[n1]=_b;
		}
	}
	int now=0,last=1;
	for(i=0;i<=n;++i)
		f[now][i]=-2000000001;
	f[now][1]=0;
	for(i=1;i<=n1;++i){
		swap(now,last);
		for(j=0;j<=n;++j)
			f[now][j]=f[last][j];
		for(j=0;j<=n;++j)
			maxi(f[now][min(n,j+a[i]-1)],f[last][j]+b[i]);
	}
	sort(c+1,c+n2+1,cmp);
	for(i=1;i<=n;++i)
		c[i]=c[i-1]+(c[i]>0?c[i]:0);
	int ans=0;
	for(j=0;j<=n;++j)
		if(f[now][j]!=-2000000001)
				maxi(ans,f[now][j]+c[j]);
	cout<<ans<<endl;
	return 0;
}