立命館合宿2012 day1 問題C Live Schedule (AOJ 1086)
制約条件
入力は全て整数
1≦C≦15
1≦D≦30
0≦W≦50
0≦X≦5
0≦Eij≦1000
0≦Fij≦10
テストケースは100個以下
ソースコード
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; }