SRM533 Div1 Easy - CasketOfStar

問題

星がn個あり、i個目の星の重さはw[i]である
「両端以外の任意の星を1つ選んで消し、その左右にある星の重みの積をスコアに加える」という操作を可能な限り繰り返す
最終的なスコアの最大値を求めよ

3 <= n <= 50
1 <= w[i] <= 1000

解法

dp[l][r]: 区間[l,r]における問題の答え
とし、r-l=2から始めて幅を増やしながら
dp[l][r] = max(dp[l][i]+dp[i][r]+w[l]*w[r]) (l＜i＜r)
という遷移をすれば解ける

class CasketOfStar {
public:
	int maxEnergy(vector<int> w) {
		int n = w.size(), dp[55][55] = {};
		reps(d,2,n) rep(l,n-d) {
			int r = l+d;
			reps(i,l+1,r) chmax(dp[l][r], dp[l][i] + dp[i][r] + w[l]*w[r]);
		}
		return dp[0][n-1];
	}
};