题目来源：POJ3280

分析

题目大意为：

给定一个长度为M（M<=2000）的小写字母串

给定串中出现的N种字母的添加和删除代价

可以在任意位置加入或删除任意字母，代价如给定

求使原串变形为回文串的最小代价

解法

刚开始的思路非常复杂，储存两个代价，并且递归处理

(left,right)之外的回文串(之间的已为回文)，然后分各种情况讨论。这又犯了想当然的毛病，而且每次都是打到一半才发现算法不完善，情况考虑未完整，影响很致命。

其实这题的解法很简单。

首先注意到当在处理(left,right)时，

如 …a(…)b… ()中为已处理完的回文串。此时删除和添加a所获得的效果和影响是一样的，因此我们只要在预处理时保留min(add[i],delete[i])就可以了。

优化

dp

详解

cost[left,right] 表示将left,right区间内字符串变成回文串

有三种情况

  1. a(…)a 这类代价直接等于(…)中代价

  2. a(…)b 有两种处理，

    后处理 a : cost[a] + cost[ (…)b ]

    后处理 b : cost[b] + cost[ a(…) ]

1
2
3
4
5
cost[left,right] =
    {  
       	cost[left+1,right-1]                                                     (if word[left]=word[right]) 
       	min( cost[left+1,right] + pay[left] , cost[left,right-1] + pay[right] )  (else                     )   
    }

细节

cost[i,i]=0 单个字符

cost[i,i-1]=0 空串

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Program Lwx;

Var 	n, m:longint;
    	word:array[1..2007] of longint;
    	cost:array[1..26] of longint;
    	tax:array[0..2007] of longint;
    	fur:array[0..2007, 0..2007] of longint;
    	i, j, k, l, x, y, z, ans:longint;
    	q, w:char;

Function min(a, b:longint):longint;
Begin
  	if a < b then exit(a); exit(b);
End;

Procedure init;
Begin
  	//assign(input, 'test.in'); reset(input);
  	readln(n, m);
  	for i := 1 to m do
  	begin
    		read(q);
    		word[i] := ord(q) - ord('a') + 1; //用数字代替字母
  	end;
  	readln;
  	for i := 1 to n do
  	begin
    		read(q);
    		readln(x, y);
    		z := ord(q) - ord('a') + 1;
    		cost[z] := min(x, y); //预处理出最小的处理代价
  	end;
  	//close(input);
End;

Procedure main;
Begin
  	for i := 0 to m do
  	for j := 0 to m do fur[i, j] := maxlongint;
  	for i := 1 to m do
  	begin
    		fur[i, i] := 0;
    		fur[i, i-1] := 0;
  	end;
  	for i := 1 to m-1 do
   	for j := 1 to m-i do
   	begin
     		l := i + j;
     		if word[j] = word[l] then begin fur[j, l] := fur[j+1, l-1]; continue; end; //若是两边字母相同
     		fur[j, l] := min(fur[j+1, l] + cost[word[j]], fur[j, l-1] + cost[word[l]]); //不同则取小的一边
   	end;
End;

Procedure outit;
Begin
	//assign(output, 'test.out'); rewrite(output);
  	write(fur[1, m]);
  	//close(output);
End;

Begin
  	init;
  	main;
  	outit;
End.