程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4283 You Are the One(區間dp)

HDU 4283 You Are the One(區間dp)

編輯：C++入門知識

HDU 4283 You Are the One(區間dp)

題意：有n個人排成一排要上台表演，每個人有一個屌絲值pi。第i個上台表演的人，他的不滿意度為(i-1)*pi。

現在有一個類似於棧的黑屋子，你可以讓某些人進入這個黑屋子。這些人要按照排的順序來，那麼對於排在最前面的人，

就有兩個選擇：

（1）讓他直接上台表演；

（2）讓他暫時進黑屋子。

現在請你選擇一個合理的調度順序，使得最後的總不滿意度最小？

訓練的時候想的是貪心，將後來想了想這樣並不對，看了題解才知道可以用區間dp來做，還是姿勢水平不夠。

思路：區間dp，對於一個區間[i, j]，區間第一個元素i可能在任意時刻上台，假設他第k個上台，那麼不管怎樣

區間[i+1, i+k-1]這k-1個元素一定在i之前上台，

區間[i+k, j]一定在i之後上台。

那麼我們就可以得到狀態轉移方程

dp(L, R) = min(dp(L+1, i)+(i-L)*ds[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L))

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
using namespace std;  

//const int maxn = 100 + 5;
const int INF = 0x3f3f3f3f;
int n;
int d[105][105], su[105];
int ds[105];

int dp(int L, int R) {
	if(L >= R) return 0;
	if(d[L][R] != -1) return d[L][R];
	d[L][R] = INF;
	for(int i = L; i <= R; i++) {
		d[L][R] = min(d[L][R], dp(L+1, i)+(i-L)*ds[L]+dp(i+1, R)+(su[R]-su[i])*(i+1-L)); 
	}
	return d[L][R];
}
int kase;
int main() {
//	freopen(input.txt, r, stdin);
	int t; cin >> t;
	while(t--) {
		memset(d, -1, sizeof(d));
		scanf(%d, &n);
		for(int i = 1; i <= n; i++) {
			scanf(%d, &ds[i]);
			su[i] = su[i-1] + ds[i];
		}
		printf(Case #%d: %d
, ++kase, dp(1, n));
	}
	return 0;
}