POJ 3280 Cheapest Palindrome DP題解

POJ 3280 Cheapest Palindrome DP題解

看到Palindrome的題目，首先想到的應該是中心問題，然後從中心出發，思考如何解決。

DP問題一般是從更加小的問題轉化到更加大的問題，然後是從地往上 bottom up地計算答案的。

能得出狀態轉移方程就好辦了，本題的狀態轉移方程是：

if (cowID[i] == cow{j]) tbl[id][i] = tbl[id][i+1];//相等的時候無需改動

else tbl[id][i] = min(tbl[!id][i+1] + cost[cowID[i]-'a'], tbl[!id][i] + cost[cowID[j]-'a']);//不相等的時候需要看改動那一邊的字符比較劃算

注意：

1 cost的刪除和插入對於DP來說實際是一樣的操作，所以只需要報出一個最小的cost就可以了

2 cost的值是以字母為下標保存值的，不是按順序給出的，也可能某些字母的值沒有給出，這個時候默認應該為零

最後是需要節省內存，這些題目一般可以只看一維dp table數組就可以了，這個時候要二維轉化為一維保存結果，實際測試內存節省非常多。

這裡使用所謂的滾動數組，輪流使用兩個數組記錄數據。

主要把二維表的斜對角格轉為一個數組保存，對應好下標就可以了。

#include 
#include 

const int MAX_M = 2001;
const int MAX_N = 26;
char cowID[MAX_M];
int cost[MAX_N];//minimum of the cost of adding and deleting that character.
int tbl[2][MAX_M];
int N, M;

inline int min(int a, int b) { return a < b ? a : b; }

int getMinCost()
{
	memset(tbl[0], 0, sizeof(int)*M);
	memset(tbl[1], 0, sizeof(int)*M);
	bool id = false;
	for (int d = 2; d <= M; d++)
	{
		id = !id;
		for (int i = 0, j = d-1; j < M; i++, j++)
		{
			if (cowID[i] == cowID[j]) tbl[id][i] = tbl[id][i+1];
			else
			{
				int c1 = tbl[!id][i+1] + cost[cowID[i]-'a'];
				int c2 = tbl[!id][i] + cost[cowID[j]-'a'];
				tbl[id][i] = min(c1, c2);
			}
		}
	}
	return tbl[id][0];
}

int main()
{
	char a;
	int c1, c2;
	while (scanf("%d %d", &N, &M) != EOF)
	{
		memset(cost, 0, sizeof(int)*N);
		getchar(); gets(cowID);
		for (int i = 0; i < N; i++)
		{
			a = getchar();
			scanf("%d %d", &c1, &c2);
			cost[a-'a'] = min(c1, c2);//only need to save the minimum
			getchar();
		}
		printf("%d\n", getMinCost());
	}
	return 0;
}