【hdu 4283】区間動的計画問題

タイトル番号:
HDU4283
タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4283
タイトルの説明:
N(N<=100)は個人的に1つの列に並んで舞台に上がり、舞台に上がる前に隣に小さな黒屋(後進先出、実はスタック)があり、隊首の人は小さな黒屋に入るか、舞台に上がるかを選ぶことができる.
一人一人がイライラ値を持ち、i番目の人のイライラ値がa[i]であれば、i番目の人の怒り値は、(K-1)*a[i]、kが最後の出場順位である.
このスタックの調整後の最終的な出場順序を求めて、すべての人の総怒り値が最小になります.図:

サンプル入力:
1 2 3 4 5
サンプル出力:
20
逆順出力総怒り値最小、すなわち5*0+4*1+3*2+2*3+1*4=20
テーマ分析:
N<=100なら基本的にダイナミックプランニングの方法ですが、
実は本質は、i人目が宿屋に入るか登場するか、暴力法のO(2^N)を選ぶので、DPを使うことを考えています
100人、単行線形で列挙可能、
区間独立性,すなわち[l,r]を満たす結果を[l,k]+k+[k+1,r]に分けることができるため,区間動的計画を用いる.
つまり全体的な考え方で、【L,R】区間は【前半区間】＋【L,R】区間1人目の最後の出場順＋【後半区間】と見ることができる
具体的には、【L,R】区間、1人目の最終出場順位がKの場合、全体の最終結果【L,R】=【L+1,K】+偏差1*K+偏差2*【K+1,R】
図:

コード内コア:dp[l][r][head];//区間[i,j]を表し、前方にhead個人が出ている最良の結果
int dpL = solve(l + 1, k, head);           int dpK = (head + k - l) * a[l];           int dpR = solve(k + 1, r, head + k - l + 1);           int sum = dpL + dpK + dpR;           dpMin = dpMin  [l,r]の最初の要素がk位置にある場合
計算dpL:最初の要素はl+1になって、最後にkで、しかも元の最初の要素は行って、あのl+1はまた新しい最初の要素になって、それではl+1の前ですでに出て行った人数は、元のlの前のheadに等しくて
計算dpK:K位置における最初の人Lの怒り値,(元の先頭head+偏差(l-k)*a[l],new head=old head+(k-l)
計算dpr:右側の最初の要素はk+1で、最後の要素はrで、new head=old head+(k-l)+1
注意headの計算
ACコード:

#include
#include

int a[101];
int dp[101][101][101];

int solve(int l , int r, int head) {
	if (l >  r) return 0;
	if (l == r) return a[l] * head;
	if (dp[l][r][head] != 0) return dp[l][r][head];
	
	int dpMin = INT_MAX;
	for (int k = l; k <= r; k++) {
		int dpL = solve(l + 1, k, head);
		int dpK = (head + k - l) * a[l];
		int dpR = solve(k + 1, r, head + k - l + 1);
		int sum = dpL + dpK + dpR;
		dpMin = dpMin < sum ? dpMin : sum;
	}
	return dp[l][r][head] = dpMin;
}

int main() {
	int ti, t;
	int i, n;
	scanf("%d", &t);
	for (ti = 0; ti < t; ti++) {
		memset(dp, 0, sizeof(dp));
		scanf("%d", &n);
		for (i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		int ans = solve(0, n - 1, 0);
		printf("Case #%d: %d
", ti + 1, ans);
	}
	return 0;
}