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からは一旦離れるかもしれない。
Get up! 明日のSUPER ST@R!