会津合宿2012 3日目 B問題 Make KND So Fat

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2012Day3&pid=B）

方針

まずは、それぞれの日について、
その日に買えるお菓子の買い方をDPにより求める。
これは、v[i]を、i円使うときの影響値の最大値として、
それを更新していくようなDPをすればいい。

これが求まったら、これを使い、
dp[i][j]を、i日目まででj円使ったときの影響値の最大値とするDPをすれば、
影響値の最大値が求まる。

ソースコード

int s, d, m;
int w[100][100], p[100][100], k[100], f[100];
int dp[101][500];

int main(){
	while(cin >> s >> d >> m){
		rep(i, s){
			cin >> k[i];
			rep(j, k[i]) cin >> w[i][j] >> p[i][j];
		}
		rep(i, d) cin >> f[i];
		
		memset(dp, 0, sizeof(dp));
		rep(i, d){
			vi v(m + 1);
			rep(j, k[f[i]]) for(int l = m - p[f[i]][j]; l >= 0; l--)
			v[l + p[f[i]][j]] = max(v[l + p[f[i]][j]], v[l] + w[f[i]][j]);
			
			rep(j, m + 1) rep(l, j + 1){
				dp[i + 1][j - l] = max(dp[i + 1][j - l], dp[i][j] + v[l]);
			}
		}
		int ans = -1, money = -1;
		for(int i = m; i >= 0; i--) if(ans < dp[d][i]) ans = dp[d][i], money = m - i;
		cout << ans << " " << money << endl;
	}
	return 0;
}