Codeforces #419 Div1 C. Karen and Supermarket

これはまぁなんとか。
http://codeforces.com/contest/815/problem/C

問題

N種の商品があり、それぞれ価格はC[i]である。
また商品に対応するクーポンを使うと価格はD[i]だけ下がる。
ただし、i番のクーポンを使うためにはP[i]番の商品を同時にクーポンを使って購入しなければならない。

所持金B以内で最大何種の商品を変えるか。

解法

クーポンの依存関係は木構造を成している。
よって子から順に以下を木DPで求めていこう。
f(v, n, b) := 頂点vのSubTree内でn個の商品を購入し、うち1つでもクーポンを使ったか否か(b)に対応する購入金額総和の最小値

SubTree中で1個でもクーポンを使用済み(b=true)の場合、vも必ず購入しなければならない。
あとはf(root,n,b)≦Bとなる最大のnを答える。

一見O(N^3)だが、実質O(N^2)になる木DPの典型問題。

int N;
int B;

int D[5050],C[5050],X[5050],V[5050];
vector<int> E[5050];
int dp[5100][5100][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B;
	FOR(i,N) {
		cin>>C[i]>>D[i];
		D[i]=C[i]-D[i];
		if(i) {
			cin>>X[i];
			X[i]--;
			E[X[i]].push_back(i);
		}
	}
	
	for(i=N-1;i>=0;i--) {
		FOR(y,N+1) dp[i][y][0]=dp[i][y][1]=1000000007;
		dp[i][0][0]=0;
		dp[i][1][0]=C[i];
		dp[i][1][1]=D[i];
		V[i]=1;
		FORR(e,E[i]) {
			for(j=V[i];j>=0;j--) {
				for(x=1;x<=V[e];x++) {
					dp[i][x+j][0]=min(dp[i][x+j][0],dp[i][j][0]+dp[e][x][0]);
					dp[i][x+j][1]=min(dp[i][x+j][1],dp[i][j][1]+min(dp[e][x][0],dp[e][x][1]));
				}
			}
			V[i]+=V[e];
		}
	}
	
	for(y=N;y>=0;y--) if(dp[0][y][0]<=B || dp[0][y][1]<=B) break;
	cout<<y<<endl;
}

まとめ

木DPを微妙に間違ってTLE連打したのが辛い。