POJ 1157 LITTLE SHOP OF FLOWERS

問題文

DP強化週間。

花がF種類あって、一列に並んだ花瓶がV個ある。
花iは花i+1より左側の花瓶に活ける必要がある。
花の種類と各花瓶に対応した点数が与えられる。
点数を最大化せよ。という問題。

dp[i + 1][j + 1]:=(花iまでを花瓶jまでにいけた時の最大の点数)
でDP。
まずはdp[i][j]はiの花瓶をjに活ける場合に

dp[i + 1][j + 1] = dp[i][j] + A[i][j];

i < jでは今までの値のほうが大きいかもしれないので

dp[i + 1][j + 1] = max(dp[i + 1][j], 
		       dp[i + 1][j + 1]);

以下ソース。

int F, V;
int A[100][100];
int dp[101][101];

int main(int argc, char **argv){
  //Input
  cin >> F >> V;
  for(int i = 0; i < F; i++)
    for(int j = 0; j < V; j++)
      cin >> A[i][j];

  memset(dp, 0, sizeof(dp));

  //DP
  for(int i = 0; i < F; i++){
    for(int j = i; j < V; j++){
      dp[i + 1][j + 1] = dp[i][j] + A[i][j];
      if(j > i)
	dp[i + 1][j + 1] = max(dp[i + 1][j], 
			       dp[i + 1][j + 1]);
    }
  }

  cout << dp[F][V] << endl;
  return 0;
}

強化週間はPOJでのDP問題を60問くらい解き終わるまで続ける。いま半分くらい。
その後は復習と別の問題を解く。POJからは一旦離れるかもしれない。