POJ 3186 Treats for the Cows
DP強化週間。
配列が与えられ、毎ターン配列の先頭か最後尾から数字を取り出せる。Tターン目に取り出した数字がaだとすると得点T * a が得られる。全ての数字を取り出したときの最大の得点を求める問題。
下の図のように
dp[i][j]:=(配列の左からi個、右からj個取り出したときの最大の得点)でDPする。
そうすると
dp[i][j] = max(dp[i - 1][j] + 左から取り出した得点, dp[i][j - 1] + 右から取り出した得点);
になる。左から(もしくは右から)は全く取り出さないケースに注意。
以下ソース。
int dp[2001][2001]; int v[2001]; int main(int argc, char **argv){ memset(dp, 0, sizeof(dp)); int n; cin >> n; for(int i = 0; i < n; i++) cin >> v[i]; dp[0][1] = v[n - 1]; dp[1][0] = v[0]; for(int i = 0; i <= n; i++){ for(int j = 0; i + j <= n; j++){ if(i - 1 < 0){ dp[i][j] = (i + j) * v[n - j] + dp[i][j - 1]; }else if(j - 1 < 0){ dp[i][j] = (i + j) * v[i - 1] + dp[i - 1][j]; }else{ dp[i][j] = max((i + j) * v[i - 1] + dp[i - 1][j], (i + j) * v[n - j] + dp[i][j - 1]); } } } int ans = 0; for(int i = 0; i < n; i++) ans = max(ans, dp[i][n - i]); cout << ans << endl; return 0; }
TopCoderの方の調子が悪い。
Get up! 明日のSUPER ST@R!