AOJ 2415: Sashimi

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";
}