TopCoder SRM 666 Div2 Hard CollectingTokens

こういう難易度の上げ方結構好き。
http://community.topcoder.com/stat?c=problem_statement&pm=13973

問題

基本設定はDiv1 Easyと同じ。
ただし、Div1 Easyは経由した頂点数なのに対し、こちらは各頂点にC[i]個のコインが置いてあり、通過した頂点の総コイン数の最大値を求める。
TopCoder SRM 666 Div1 Easy WalkOverATree - kmjp's blog

解法

今度はDiv1 Easyのような貪欲解法は取れない。
こちらは素直にDPで行う。
各頂点iにおいて、dp[i][残移動回数][頂点iに戻るor戻らない] := 頂点i以下における総コイン枚数、としてDPを行う。
各頂点から各子頂点を探索するとき、頂点iに戻らない選択肢を取れるのは最大1回である、としてDPをしていけば良い。

なお、Div1 EasyでもこのDPをしていた人は結構いた。

int N;
int dp[101][101][2];
int T[101];
vector<int> E[101];

class CollectingTokens {
	public:
	
	void dfs(int cur,int pre,int L) {
		dp[cur][0][0]=dp[cur][0][1]=T[cur];
		int i,x;
		
		FORR(r,E[cur]) if(r!=pre) {
			dfs(r,cur,L);
			
			for(x=L;x>=0;x--) {
				for(i=L;i>=0;i--) {
					if(x+1+i<=L) dp[cur][x+1+i][1] = max(dp[cur][x+1+i][1],dp[cur][x][0]+dp[r][i][1]);
					if(x+2+i<=L) dp[cur][x+2+i][1] = max(dp[cur][x+2+i][1],dp[cur][x][1]+dp[r][i][0]);
					if(x+2+i<=L) dp[cur][x+2+i][0] = max(dp[cur][x+2+i][0],dp[cur][x][0]+dp[r][i][0]);
				}
			}
		}
	}
	
	int maxTokens(vector <int> A, vector <int> B, vector <int> tokens, int L) {
		MINUS(dp);
		int i;
		N=A.size()+1;
		FOR(i,N) E[i].clear(), T[i]=tokens[i];
		FOR(i,N-1) E[A[i]-1].push_back(B[i]-1),E[B[i]-1].push_back(A[i]-1);
		
		dfs(0,-1,L);
		int ma=0;
		FOR(i,L+1) ma=max(ma,dp[0][i][1]);
		return ma;
	}
};

まとめ

Div1 Easyは自分も最初このDPを思いついたけど、思いとどまって良かった。
…と思ったらDiv2 Hardで結局このDPを書く羽目に。