yukicoder : No.54 Happy Hallowe'en

実装は簡単だが、考察が若干難しい。
http://yukicoder.me/problems/41

問題

太郎君は初期状態でキャンディーを0個持つ。
i番目の家を訪問したとき、所持キャンディー数がT[i]未満ならV[i]個もらえる。

各家は１回ずつまでしか訪問できないが、訪問順は任意である。
太郎君が得られる最大キャンディー数はいくつか。

解法

訪問する家の順番さえ決めてしまえば、あとは単純なDPである。
よって家の訪問順を考察してみる。

家1と家2があったとき、家1を優先した方がいい条件、すなわち家1に先に行けば(V[1]+V[2])個キャンディーが得られて、家2に先に行くとV[2]個しか得られない(家1訪問時にT[1]個を超えてしまう)場合を考える。
家1,2に行く前のキャンディー数をCとする。(C＜T[1]、C＜T[2]は前提としておく)

• 家1に行ったあと家2に行ってキャンディーをもらえる条件: C + V[1] ＜ T[2]
• 家2に行ったあと家1に行ってキャンディーをもらえない条件: C + V[2] ≧ T[1]

上の２式より、T[1]-V[2]≦C＜T[2]-V[1]なので、変形してV[1]+T[1]＜V[2]+T[2]。
すなわちV+Tが小さい方に先に行く方が、最終的に良い結果が得られることが分かった。
後は前述のとおりDPでキャンディー数を求めるだけ。

int N,V[10002],T[10002];
int ok[20001];
pair<int,int> P[10001];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) cin>>V[i]>>T[i];
	FOR(i,N) P[i]=make_pair(V[i]+T[i],i);
	sort(P,P+N);
	
	ok[0]=1;
	FOR(i,N) for(x=T[P[i].second]-1;x>=0;x--) if(ok[x]) ok[x+V[P[i].second]]=1;
	
	
	for(i=20000;i>=0;i--) if(ok[i]) break;
	_P("%d\n",i);
}

まとめ

このように「どの順で訪問するのがベストかわからない」という問題は、まずは２つの訪問先においてどちらかを優先すると特になる条件式を求め、その式の値によって訪問先をソートするとよい。

antaさんの解説では類題としてSRM610 Div1 Mediumを挙げていたね。