便宜的回文 (USACO 2007)(c++)
2019-08-21便宜的回文(USACO 2007)
内存限制:128 MiB 时间限制:1000 ms 标准输入输出
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。 题目类型:传统 评测方式:文本比较
题目描述
追踪每头奶牛的去向是一件棘手的任务,为此农夫约翰安装了一套自动系统。他在每头牛身上安装了一个电子身份标签,当奶牛通过扫描器的时候,系统可以读取奶牛的身份信息。目前,每个身份都是由一个字符串组成的,长度为M (1≤M≤2000),所有的字符都取自小写的罗马字母。
奶牛们都是顽皮的动物,有时她们会在通过扫描器的时候倒着走,这样一个原来身份为abcb的奶牛就可能有两个不同的身份了(abcb和bcba),而如果身份是abcba的话就不会有这个问题了。
约翰想改变奶牛们的身份,使他们不管怎么走读起来都一样。比如说,abcb可以在最后加个a,变成回文abcba;也可以在前面加上bcb,变成回文bcbabcb;或者去除字母a,保留的bcb也是一条回文。总之,约翰可以在任意位置删除或插入一些字符使原字符串变成回文。
不巧的是,身份标签是电子做的,每增加或删除一个字母都要付出相应的费用(0≤代价≤10000)。给定一头奶牛的身份标签和增加或删除相关字母的费用,找出把原来字符串变成回文的最小费用。注意空字符串也是回文。
输入格式
第一行:两个用空格分开的整数:N和M 第二行:一个长度恰好为M的字符串,代表初始的身份标签 第三行到第N+2行:每行为一个用空格分开的三元组:其中包括一个字符和两个整数,分别表示增加或删除这个字符的费用
输出格式
第一行:只有一个整数,表示改造这个身份标签的最小费用
样例
样例输入
3 4
abcb
a 1000 1100
b 350 700
c 200 800
样例输出
900
代码如下
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <cstdlib> 7 using namespace std; 8 int cn,n,ab[30],f[2010][2010]; 9 char a[2010]; 10 11 int main () { 12 scanf ("%d%d",&cn,&n); 13 scanf ("%s",a+1); 14 for (int i=1;i<=cn;i++) { 15 char ca; 16 scanf (" %c",&ca); 17 int x,y; 18 scanf ("%d%d",&x,&y); 19 ab[ca-'a']=min(x,y); 20 } 21 for (int i=2;i<=n;i++) { 22 for (int j=i-1;j>0;j--) { 23 if (a[i]==a[j]) { 24 f[j][i]=f[j+1][i-1]; 25 } 26 else { 27 f[j][i]=min(f[j+1][i]+ab[a[j]-'a'],f[j][i-1]+ab[a[i]-'a']); 28 } 29 } 30 } 31 cout << f[1][n]; 32 return 0; 33 }
分析
读入don't have too mach to say. 注意%c签的' '(空格);
定义:a[] 为牌号
ab[] 为牌号的最小价值 (因为不管是添加或删去,都应选价格最小的)
f[ j ][ i ] 为a[ j ] 到 a[ i ] 的最小价值
动态转移方程 :f[ j ][ i ]= f[ j+1 ][ i-1 ] (if (a[ i ] == a [ j ]) )
min(f[ j+1][ i ]+ad[ a[ j ]-'a'],f[ j ][ i-1 ]+ad[ a[i]-'a' ]) (if (a[ i ] != a[ j ])
初始化 : f [ i ] [ i ]=0 第i个共一个字符,一定是回文词,花费0
设
a | b | c | b | c |
1 | 2 | 3 | 4 | 5 |
若 j=2 && i=4 时 :
a [ i ]==a [ j ] 所以费用不用变动 f [j ][ i ]=f [j+1] [i -1] =f [3] [3]=0;
若 j=1 && i=5 :
a[ i ]!=a[ j ] 方案1:在f [ 2 ] [ 4 ] 的基础上 增删 a [ j ] 使其为 bcb 或 abcba
方案2:在f [ 2 ] [ 4 ] 的基础上 增删 a [ i ] 使其为 bcb 或 cbcbc
所以 f [ j ] [ i ]=min( f [ j+1 ] [ i ]+ab[ a[ j ]-'a'],f [ j ] [ i-1 ]+ab[ a[ i ]-'a']);
综上所述 :f [ 1 ] [ n ] 为解