yukicoder : No.37 遊園地のアトラクション

★３なのでどんどん行きます。
http://yukicoder.me/problems/63

問題

N個のアトラクションがある。
各アトラクションの待ち時間はC[i]である。
また、各アトラクションの初回利用時の満足度はV[i]である。

ここで、時間Tの間に出来るだけ多くの満足度を得たい。
１つのアトラクションを待ってる間は、当然他のアトラクションを待つことはできない。
また、同じアトラクションを（またC[i]待って）複数回遊ぶこともできるが、前回の満足度の半分(小数切捨て)しか満足度を得られない。

時間Tで得られる最大の満足度はいくらか。

解法

i番のアトラクションで得られる満足度と待ち時間の関係は以下のようになる。

回数	合計待ち時間	合計満足度
1	C[i]
2	2*C[i]
3	3*C[i]	+ \lfloor \frac{V\[i\]}{4} \rfloor ]]
	以下同様

満足度は最大500なので、アトラクションの利用回数は高々9回で打ち止めとなる。
あとはこの合計待ち時間の中で合計満足度を高める問題なので単なるナップサック問題であり、DPで解ける。

int T,N;
int C[101],V[101],VS[101][14];
int DP[16][10010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T>>N;
	FOR(i,N) cin>>C[i];
	FOR(i,N) {
		cin>>V[i];
		FOR(j,13) {
			VS[i][j+1]=VS[i][j]+V[i];
			V[i]/=2;
		}
		FOR(j,T+1) FOR(x,11) if(j+x*C[i]<=T)
			DP[i+1][j+x*C[i]]=max(DP[i+1][j+x*C[i]],DP[i][j]+VS[i][x]);
	}
	cout << *max_element(DP[N],DP[N]+T+1) << endl;
}

まとめ

このあたりは本番参戦する前なので、思い入れは少な目。