AT_dp_x Tower

struct Node{
	int w,s,v;
}t[N];

bool cmp(Node a,Node b){
	return a.w+a.s>b.w+b.s;
}

int f[N];//（考虑了前i个）上面的重量和上限为j时的最大价值

signed main(){
	int n=rd;
	for(int i=1;i<=n;i++){
		t[i]={rd,rd,rd};
	}
	
	
	sort(t+1,t+n+1,cmp);
	
	// memset(f,-0x3f3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++){
		// cdbg(t[i].s);
		for(int j=t[i].w;j<=M;j++){
			// if(i==2&&min(t[i].s,j-t[i].w)==2)cdbg("OK");
			f[min(t[i].s,j-t[i].w)]=max(f[min(t[i].s,j-t[i].w)],f[j]+t[i].v);
		}
		// cdbg(f[2]);
	}
	int ans=0;
	for(int i=0;i<=M;i++)ans=max(ans,f[i]);
	cout<<ans<<endl;
}

其中M=10000，会WA #6，但是开20000就过了。结合题中s,w<10001，有些不理解。

f[j] 表示（考虑了前i个物品时）且要求后面加上的那个物品的w的上限为i时的最大价值。