Submission #6614876

---

Source Code Expand

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

const ll INF = 1145141919810893;

int N;
ll dp[400][400];
ll cost[400];
ll ruisekiwa[401];//idx i ~ idx j (i < j)は [i, j)

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> cost[i];
		ruisekiwa[i + 1] = cost[i] + ruisekiwa[i];
	}
	for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)dp[i][j] = INF;

	for (int i = 0; i < N; i++)dp[i][i] = 0;

	for (int i = 1; i < N; i++) {
		for (int j = 0; j + i < N; j++) {
			ll ans = INF;
			if (i == 1) {
				dp[j][j + i] = ruisekiwa[j + i + 1] - ruisekiwa[j];
			}
			else {
				for (int k = j; k <= j + i - 1; k++) {
					int ll = j, lr = k, rl = k + 1, rr = j + i;
					ans = min(ans, dp[ll][lr] + dp[rl][rr]);
				}
				ans += ruisekiwa[j + i + 1] - ruisekiwa[j];
				dp[j][j + i] = ans;
			}
		}
	}
	
	cout << dp[0][N - 1] << endl;
	return 0;
}

Submission Info

Judge Result