http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415
monge(もんじゅ)dp。
http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915
と
http://sssslide.com/www.slideshare.net/ikumihide/ss-50881829
を参考にした。
単調性が本質で、それをうまく利用するため対角線上にdpを更新していく感じ。
int N; ll dp[MAX_N][MAX_N]; int A[MAX_N][MAX_N]; ll S[MAX_N]; void solve() { cin >> N; rep(i, 0, N) { cin >> S[i + 1]; S[i + 1] += S[i]; } rep(i, 0, N) { A[i][i] = i; } rep(k, 1, N) { rep(i, 0, N - k) { int j = i + k; int a = A[i][j - 1]; int b = A[i + 1][j]; ll m = inf; ll at = -1; for(int l = a; l <= b; l++) { if(i > l || l >= j) continue; ll tm = dp[i][l] + dp[l + 1][j]; if(tm <= m) { at = l; m = tm; } } dp[i][j] = m + S[j + 1] - S[i]; A[i][j] = at; } } cout << dp[0][N - 1] << "\n"; }