Cheapest Palindrome [POJ3280] [区间DP] [经典]

一句话题意：每个字母添加和删除都相应代价（可以任意位置增加/删除），求把原串变成回文串的最小代价

Description

保持对所有奶牛的跟踪是一项棘手的任务，因此农场主约翰已经安装了一个系统来实现自动化。他在每头奶牛身上安装了一个电子ID标签，系统将在奶牛经过扫描仪时读取。每个ID标记是从字母表中提取的一个字符串。

奶牛，它们是淘气的动物，有时试图通过倒着走来欺骗系统。如果一头奶牛的ID是“abcba”，那么无论她怎么走，它都能读到同样的东西，而拥有“abcb”的奶牛可能会注册为两个不同的ID(“abcb”和“bcba”)。

FJ希望改变奶牛的ID标签，这样无论奶牛走过哪个方向，他们都能读到同样的标签。例如，“abcb”可以通过在末尾添加“a”来改变，从而形成“abcba”，这样ID就会是一个回文串。更改ID的其他一些方法包括将三个字母“bcb”添加到“abcb”的开始，以获得ID“bcbabcb”或删除字母“a”以产生ID“bcb”。我们可以在字符串中的任意位置添加或删除字符，其长度比原来的字符串长或短。

不幸的是，ID标签是电子信息，每个字符插入或删除都有代价，这取决于要添加或删除的字符值。考虑到奶牛ID标签的内容以及插入或删除字母表中的每个字符的成本，找到更改ID标记的最小成本，从而满足FJ的需求。一个空的ID标签被认为满足了读取前后相同的要求。只有带有相关成本的字母才能添加到字符串中。

Input

Line 1: 两个空间分隔的整数:N和M (1 ≤ M ≤ 2,000) (1 ≤ N ≤ 26)
Line 2: 这一行包含了组成初始ID字符串的M个字符

Lines 3..
N+2: 每行包含三个空间分隔的实体:输入字母和两个整数的字符，分别是添加和删除该字符的成本(Ci<=10000)。

Output

Line 1: 单个整数的一行，这是更改给定名称标签的最小代价。

Sample Input

3 4

abcb

a 1000 1100

b 350 700

c 200 800

Sample Output

Hint

如果我们在最后插入一个“a”，得到“abcba”，成本是1000。如果我们在开始的时候删除“a”，就会得到“bcb”，代价就是1100。如果我们在字符串的开始处插入“bcb”，代价将是350 + 200 + 350 = 900，这是最小值。

Solution

首先，这是一个很明显的区间问题

如果一个区间[i,j]已经是回文序列了，就很好处理。

那我们设dp[i][j]为，使区间[i,j]成为回文序列的最小代价

当s[i-1]==s[j+1]时，dp[i+1][j-1]=dp[i][j]

其他情况：dp[i-1][j]=dp[i][j]+min(del[s[i-1]],add[s[i-1]])

　　　　　dp[i][j+1]=dp[i][j]+min(del[s[j+1]],add[s[j+1]])

tips:我们输入的时候就保留增加和减小的最小值

Code

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;i++)

 #define per(i,a,b)    for(RG i=a;i>=b;i--)

 #define inf (1<<30)

 using namespace std;

 int n,m;

 int val[],dp[][];

 char s[];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void DP()

 {

     rep(k,,m)

     {

         for(RG i=,j=k;j<=m;j++,i++)

         {

             dp[i][j]=inf;

             if(s[i]==s[j])    dp[i][j]=dp[i+][j-];

             else

             {

                 dp[i][j]=min(dp[i][j],dp[i+][j]+val[s[i]]);

                 dp[i][j]=min(dp[i][j],dp[i][j-]+val[s[j]]);

             }

         }

     }

     printf("%d",dp[][m]);

 }

 int main()

 {

     char ch;int x,y;

     n=read(),m=read();

     scanf("%s",s+);

     rep(i,,n)    cin>>ch,x=read(),y=read(),val[ch]=min(x,y);

     DP();

     return ;

 }

秒客网

Cheapest Palindrome [POJ3280] [区间DP] [经典]

相关文章