学步园

【题意】

给定一个长度为m(m<=2000)的小写字母字符串，在给定组成该字符串的n(n<=26)个字符的添加和删除费用，求使原字符串变为回文串的最小费用

【输入】

第一行n,m

第二行原字符串

接下来n行开头一个小写字母，然后两个数字分别表示添加删除该字母的费用

【输出】

输出一个数字，表示最小费用

动态规划

用f[i][j]表示将i到j变为回文串的最小费用

转移方程为

f[i,j]=min(f[i+1,j]+min(costd[s[i]],costi[s[i]]),f[i,j-1]+min(costd[s[j]],costi[s[j]]))

若s[i]=s[j]则还需考虑f[i+1,j-1]的值

program poj3280;
var
  n,m,i,j,k:longint;
  costd,costi:array ['a'..'z'] of longint;
  f:array [0..2001,0..2001] of longint;
  s:ansistring;
  who:char;

function min (a,b:longint):longint;
begin
  if a<b then exit(a)
         else exit(b);
end;

begin
  readln(n,m);
  readln(s);
  for i:=1 to n do
    readln(who,costi[who],costd[who]);
  fillchar(f,sizeof(f),63);
  for i:=1 to m do
    begin
      f[i,i]:=0;
      f[i,i-1]:=0;
    end;
  for i:=2 to m do
    for j:=1 to m-i+1 do
      begin
        if s[j]=s[j+i-1] then f[j,j+i-1]:=min(f[j,j+i-1],f[j+1,j+i-2]);
        f[j,j+i-1]:=min(f[j,j+i-1],f[j+1,j+i-1]+costd[s[j]]);
        f[j,j+i-1]:=min(f[j,j+i-1],f[j+1,j+i-1]+costi[s[j]]);
        f[j,j+i-1]:=min(f[j,j+i-1],f[j,j+i-2]+costd[s[j+i-1]]);
        f[j,j+i-1]:=min(f[j,j+i-1],f[j,j+i-2]+costi[s[j+i-1]]);
      end;
  writeln(f[1,m]);
end.