UVA - 10003 - Cutting Sticks （區間DP）

UVA - 10003 - Cutting Sticks （區間DP）

這裡簡述一下區間DP：

主要思想：

區間動態規劃問題一般都是考慮對於每段區間，他們的最優值都是由幾段更小區間的最優值得到，是分治思想的一種應用，將一個區間問題不斷劃分為更小的區間直至一個素組成的區間，枚舉他們的組合，求合並後的最優值。

定義狀態：設dp[i][j]為區間i,j之間的最小代價（實際看題意）

實現過程：

for(int p = 1 ; p <= n ; p++) { //p是區間的長度，作為階段

for(int i = 1 ; i <= n ; i++) { //i是窮舉區間的起點

int j = i+p-1; //j為區間的終點

for(int k = i ; k < j ; k++) //狀態轉移

dp[i][j] = min{dp[i][k]+dp[k+1][j]+w[i][j]};//這個是看題目意思，有的是要從k開始不是k+1

dp[i][j]= max{dp[i][k]+dp[k+1][j]+w[i][j]};

}

}

對於這一題來說：首先得明確狀態轉移方程為dp[i][j]=min(dp[i][k],dp[k][j])+num[j]-num[i] (i

AC代碼：

#include 
#include 
#include 
#include 
#include 
#define INF 0x3fffffff
using namespace std;

const int maxn = 60;
int dp[maxn][maxn];	//dp[i][j]代表在區間i,j之間的最小代價 
int num[maxn];

int main() {
	int L, n;
	while(scanf("%d", &L) && L) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%d", &num[i]);
		num[0] = 0;
		num[n + 1] = L;
		memset(dp, 0, sizeof(dp));
		for(int p = 1; p <= n + 1; p++)
			for(int i = 0; i <= n + 1; i++) {
				int j = i + p;
				int MIN = INF;
				if(j > n + 1) break;
				for(int k = i + 1; k < j; k++) {
					int tmp = dp[i][k] + dp[k][j] + num[j] - num[i];
					MIN = min(MIN, tmp);
				}
				if(MIN != INF) dp[i][j] = MIN;
			}
		
		printf("The minimum cutting is %d.\n", dp[0][n + 1]);
	} 
	return 0;
}