[USACO07OPEN]便宜的回文Cheapest Palindrome

佚名 6年前 (2019-04-10) 随笔 694人围观抢沙发百度已收录

字串S长M，由N个小写字母构成。欲通过增删字母将其变为回文串，增删特定字母花费不同，求最小花费。

题目描述见上

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

显然这是一道区间DP

从两头DP，枚举长度啥的很套路了。具体细节请参见代码qwq

[USACO07OPEN]便宜的回文Cheapest Palindrome 随笔第1张

 1 #include<iostream> 
 2 #include<cstdio>
 3 #include<cstring>
 4 #define re register int
 5 #define maxn 2000+5
 6 #define maxn1 3000+5
 7 int val[maxn],dp[maxn1][maxn1],val1,val2;
 8 char ch[maxn1],temp[3];
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,f=1;
13     char ch=getchar();
14     while(!isdigit(ch))
15     {
16         if(ch=='-') f=-1;
17         ch=getchar();
18     }
19     while(isdigit(ch))
20     {
21         x=(x<<3)+(x<<1)+ch-'0';
22         ch=getchar();
23     }
24     return x*f;
25 }
26 int main()
27 {
28     int n,m;
29     memset(dp,0x3f,sizeof(dp));//必须要初始化 
30     n=read();
31     m=read();
32     scanf("%s",ch+1);
33     for(re i=1;i<=n;i++)
34     {
35         cin>>temp[0];
36         val1=read();
37         val2=read();
38         val[temp[0]-'a']=min(val1,val2);
39         //易得从中间插入或删除是等效的 
40     }
41     for(re i=1;i<=m;i++)
42     {
43         dp[i][i]=0;
44         if(ch[i]==ch[i+1]) dp[i][i+1]=0;
45     }
46     for(re len=0;len<=m;len++)
47     //len必须从0枚举
48     //否则会少算情况（连样例都过不了QAQ） 
49     for(re i=1;i<=m;i++)
50     {
51         int j=len+i;
52         int x1=ch[i-1]-'a';
53         int x2=ch[j+1]-'a';
54         if(x1==x2) dp[i-1][j+1]=min(dp[i-1][j+1],dp[i][j]);
55             dp[i-1][j]=min(dp[i-1][j],dp[i][j]+val[x1]);
56             dp[i][j+1]=min(dp[i][j+1],dp[i][j]+val[x2]);
57            //每种状态都需要算一遍
58            //因为不知道会从哪个扩展 
59     }
60     cout<<dp[1][m];
61     return 0;
62     
63 }