mayoko’s diary

プロコンとかいろいろ。

SRM 533 div1 easy: CasketOfStar

解法

区間 DP で解くことが出来ます。

dp[l][r] = (区間 [l, r] において得ることの出来るスコアの最大値) とします。

区間 [l, r] の中では, 最後に残るのは, l 番目と r 番目の数です。最後に m 番目(l < m < r)の数が消されるとすると, この操作によって得られるスコアは weight[l] * weight[r] となります。で, その前には [l, m] 番目の区間と [m, r] 番目の区間で操作していたことになります。m 番目の数を残しておいているとすると, [l, m] 区間と [m, r] 区間を介した操作をすることが出来ないので問題を分割出来るんですね。

区間の幅が 2 以下の時は dp[l][r] = 0 で, 最終的には dp[0][n-1] を答えとすれば良いですね。

int dp[55][55];

class CasketOfStar {
public:
    int maxEnergy(vector <int> weight) {
        int n = weight.size();
        memset(dp, 0, sizeof(dp));
        for (int w = 3; w <= n; w++) {
            for (int l = 0; l+w <= n; l++) {
                int r = l+w-1;
                dp[l][r] = weight[l]*weight[r];
                int tmp = 0;
                for (int i = l+1; i < r; i++) tmp = max(tmp, dp[l][i] + dp[i][r]);
                dp[l][r] += tmp;
            }
        }
        return dp[0][n-1];
    }
};