立命館合宿2012 day1 問題C Live Schedule (AOJ 1086)

問題

日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1086

制約条件

入力は全て整数
1≦C≦15
1≦D≦30
0≦W≦50
0≦X≦5
0≦Eij≦1000
0≦Fij≦10


テストケースは100個以下

方針

動的計画法による。
dp[i][j][k]を、i日目までで、疲労度jで、k回一日に2つ以上の会場でライブをしたときの利益の最大値とする。


これを愚直に更新するようなDPをすればよい。

ソースコード

int c,d,w,x;
int e[40][40],f[40][40];
int dp[31][51][6];
int main(){
	while(cin>>c>>d>>w>>x, c){
		rep(i,c)rep(j,d)cin>>e[i][j];
		rep(i,c)rep(j,d)cin>>f[i][j];
		memset(dp,-1,sizeof(dp));
		dp[0][0][0]=0;
		
		rep(i,d)rep(j,w+1)rep(k,x+1){
			rep(l,c){
				int nj=j, m=l, nk=k, nxt=dp[i][j][k];
				while(m<c){
					nj+=f[m][i]; nxt+=e[m][i];
					if(nk>x||nj>w||e[m][i]==0)break;
					dp[i+1][nj][nk]=max(dp[i+1][nj][nk],nxt);
					nk=k+1; m++;
				}
			}
			dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
		}
		int ans=0;
		rep(i,w+1)rep(j,x+1)ans=max(ans,dp[d][i][j]);
		cout<<ans<<endl;
	}
	return 0;
}