Cheapest Palindrome POJ 3280(区间dp)

原题

题目链接

题目分析

有点难度的区间dp题,可以这样定义dp[i][j],把s[i-j]变为回文串的最小花费,显然s[i][i]=0,先说一下删除字母和添加字母的处理,因为当s[i-j]是回文串的时候,再往外扩展一个字母有两种方法,一种是删除这个字母,另一种是再添加一个字母,因此输入删除字母和添加字母的价格只需要保留花费小的就行了,下面用cost[i]表示.考虑dp[i][j],有三种更新方向,往右扩展,dp[i][j+1]=min(dp[i][j]+cost[s[j+1]-‘a‘],dp[i][j+1]),往左扩展,dp[i-1][j]=min(dp[i][j]+cost[s[i-1]-‘a‘],dp[i-1][j]),如果s[i-1]==s[j+1],则有dp[i-1][j+1]=min(dp[i-1][j+1],dp[i][j]).把dp的更新图画出来可以发现对于dp[i][j],按状态来源方向有dp[i][j]=min(dp[i+1][j]+cost[s[i]-‘a‘],dp[i][j-1]+cost[s[j]-‘a‘]),如果s[i]==s[j],有dp[i][j]=min(dp[i][j],dp[i+1][j-1]).按上述dp[i][j]状态来源方向可以更简单的处理问题(如果要按更新方向的话需要注意‘aa‘这样的问题,处理一下也能ac).最后答案是dp[0][M].

代码

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <utility>
 6 #include <ctime>
 7 #include <cmath>
 8 #include <cstring>
 9 #include <string>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <set>
14 #include <map>
15 
16 using namespace std;
17 typedef long long LL;
18 const int INF_INT=0x3f3f3f3f;
19 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
20 
21 int n,m;
22 char s[3000];
23 int add[30],de[30],cost[30];
24 int dp[3000][3000];
25 
26 int main()
27 {
28 //    freopen("black.in","r",stdin);
29 //    freopen("black.out","w",stdout);
30     scanf("%d %d",&n,&m);
31     scanf("%s",&s);
32     getchar();
33     for(int i=0;i<n;i++)
34     {
35         char x;
36         scanf("%c",&x);
37         scanf("%d %d",&add[x-‘a‘],&de[x-‘a‘]);
38         cost[x-‘a‘]=min(add[x-‘a‘],de[x-‘a‘]);
39         getchar();
40     }
41     for(int i=m-1;i>=0;i--)
42     {
43         for(int j=i+1;j<m;j++)
44         {
45             dp[i][j]=INF_INT;
46             dp[i][j]=min(dp[i+1][j]+cost[s[i]-‘a‘],dp[i][j-1]+cost[s[j]-‘a‘]);
47             if(s[i]==s[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
48         }
49     }
50 /*    for(int j=0;j<m;j++)
51     {
52         for(int i=0;i<=j;i++) printf("dp[%d][%d]=%d ",i,j,dp[i][j]);
53         cout<<endl;
54     }*/
55 
56     printf("%d\n",dp[0][m-1]);
57     return 0;
58 }