AOJ 1086 : Live Schedule

問題リンク：Live Schedule | Aizu Online Judge

解法：
動的計画法

dp[何日目か][負担][連続してライブをした日数] := 最大利益　とする

遷移の状態としては、
・何もしない
・その場所だけでライブ
・連続してライブ
の３つがある

Eが0の時はそこでライブを行えない亊に注意
連続してライブを行う際に途中でEが０になったらbreakする亊を忘れないように

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 40

using namespace std;

int C,D,W,X;
int E[MAX][MAX];
int F[MAX][MAX];
int dp[40][60][10];//dp[D:day][W:burden][X:kurenai]

int main()
{
  while(scanf("%d %d %d %d",&C,&D,&W,&X),C|D|W|X)
    {  
      rep(i,C)rep(j,D)scanf("%d",&E[i][j]);
      rep(i,C)rep(j,D)scanf("%d",&F[i][j]);  

      rep(i,40)rep(j,60)rep(k,10)dp[i][j][k] = -inf;
      dp[0][0][0] = 0;

      rep(day,D)
	{
	  rep(burden,W+1)
	    {
	      rep(x,X+1)
		{
		  //何もしない
		  dp[day+1][burden][x] = max(dp[day+1][burden][x],
					     dp[day  ][burden][x]);

		  rep(region,C)
		    {
		      if(E[region][day] == 0)continue;
		      
		      //そこでラヴライヴ
		      if(burden + F[region][day] <= W)
			{
			  dp[day+1][burden+F[region][day]][x] = max(dp[day+1][burden+F[region][day]][x],
								    dp[day][burden][x]+E[region][day]);
			}

		      //ラブライブ！
		      int cost = 0;
		      int value = 0;
		      
		      for(int cur=region;cur>=0;cur--)
			{
			  cost  += F[cur][day];
			  value += E[cur][day];
			  if(cur == region)continue;
			  if(E[cur][day] == 0)break;
			  if(burden + cost <= W && x + 1 <= X)
			    {
			      dp[day+1][burden+cost][x+1] = max(dp[day+1][burden+cost][x+1],
								dp[day  ][burden     ][x  ]+value);
			    }
			  else break;
			}
		      
		      cost = 0;
		      value = 0;
		      for(int cur=region;cur<C;cur++)
			{
			  cost  += F[cur][day];
			  value += E[cur][day];
			  if(E[cur][day] == 0)break;
			  if(cur == region)continue;
			  if(burden + cost <= W && x + 1 <= X)
			    {
			      dp[day+1][burden+cost][x+1] = max(dp[day+1][burden+cost][x+1],
								dp[day  ][burden     ][x  ]+value);
			    }
			  else break;
			}
		      
		    }

		}
	    }
	}

      int ans = 0;
      rep(i,W+1)rep(j,X+1)
	{
	  ans = max(ans,
		    dp[D][i][j]);
	}
      printf("%d\n",ans);

    }
  return 0;
}