POJ-3280 Cheapest Palindrome[转]

来源:互联网 时间:1970-01-01

这个dp题可以算是很顺利的一题,虽说之前看了看就觉得很难没管它,但是今天真的不一样,开始其实思路还有点乱麻,只过了几分钟我忽然间就理清了思路,得到了一个dp子问题,可能还要归功于之前做了一题叫括号匹配的类似dp给了我灵感,真的构造出来和没有构造出前的差别很大啊!

同学们!相信自己的实力吧!但是要自信加合理推导才能得出信服的答案!

其实dp很难逃出3种思路:

1、一维线性dp:每次考虑i时,选择最优子问题要么在i-1,要么在1...i-1里;

2、二维线性dp:考虑(i,j)子问题时,选择最优子问题要么在(i+1,j)、(i,j-1),要么在i<= k <=j,在k里;

3、树形dp:考虑i节点最优时,选择子节点最优,一般融合了01背包dp的双重dp。

上面3中模式也是我在做题后才发现的。

这个dp题其实就可以仿照第2中思路。

假设一个字符串Xx....yY;对于求这个字符串怎么求呢?

分4中情况讨论:

1、去掉X,取x....yY回文;

2、去掉Y,取Xx....y回文;

3、在左边加上X,取Xx....yYX回文;

4、在右边加上Y,取YXx....y回文。

至于去掉X、Y肯定没有第1、2中情况合算;加上X、Y肯定没有第3、4中情况合算。

因此令dp[i][j]为i...j要变成回文字符串的最小代价。

方程:

dp[i][j] = min{  dp[i+1][j] + {去掉X的代价},dp[i+1][j] + {加上X的代价},

                                                           dp[i][j-1]+ {去掉Y的代价},dp[i][j-1] +{加上Y的代价}};

其实分析发现,对于X而言,只要去 去掉 和加上 X 最小代价就行(因为前面dp串一样),Y同理。

因此最后得出:

dp[i][j] = min{  dp[i+1][j] +min{ {去掉X的代价}, {加上X的代价}},

                                                           dp[i][j-1]+min{ {去掉Y的代价}, {加上Y的代价}}};

dp时候还有些注意事项:

比如当X和Y字符一样时,则在dp时必须先为x...y的最小代价。

读取时也应注意。

代码:


#include <iostream>
using namespace std;

#define  N 2000+5
#define  inf 0x7fffffff
int dp[N][N],n,m,a[30];
char ch[N],c[100];
int cpu(int &j)//将字符串转换为整型数
{
 int d= 0;
 while(c[j] != ' ' && c[j] !=0)
 {
  d *= 10;
  d += (c[j]-'0');
  j++;
 }
 return d;
}
int main()
{
 freopen("E://yhy.txt","r",stdin);
 freopen("E://yyy.txt","w",stdout);
 
 scanf("%d %d",&m,&n);
 scanf("%s",ch);
 
 cin.getline(c,100);
 int i,k,j;
 int add,del;
 for(i = 1; i <= m ;i++)
 {
  cin.getline(c,100);//读取一行
  j = 2;
  add = cpu(j);
  j++;
  del = cpu(j);
  a[c[0]-'a']= min(add,del);//存储添加和删除字符的最小代价
 }


 for(i = 1; i <= n ;i++)//初始化间隔为0的情况
  dp[i][i] = 0;

 for(k = 1; k <n ;k++)//k为间隔
 {
  for(i = 1; i < n;i++)//起始字符位置
  {
   if(i +k >n)break;
   
   dp[i][i+k] = inf;
   if(ch[i-1] == ch[i+k-1])//如果首字符和尾字符一样时先对dp赋值,保证最优
   {
    if(k == 1)//如果间隔为1
     dp[i][i+k] = 0;
    else //否则去中间回文代价
     dp[i][i+k] =dp[i+1][i+k-1];
   }

   dp[i][i+k] = min(dp[i][i+k],
    min(dp[i+1][i+k] + a[ch[i-1]-'a'],dp[i][i+k-1] + a[ch[i+k-1]-'a']));//dp方程
  }
 }

 cout<<dp[1][n];
 return 0;
}

另附:my code :

/*
 * 3280.cpp
 *
 *  Created on: 2011-7-6
 *      Author:
 */


#include <iostream>
using namespace std;

const int MAXM = 2000 + 5;
const int MAXN = 26 + 5;

int n, m;
char str[MAXM] = {};
int cost[1000][2] = {};
int d[MAXM][MAXM] = {};

int main(){
    cin >> n >> m >> str;
    for(int i=0; i<n; i++){
        char tmp;
        cin >> tmp;
        cin >> cost[tmp][0] >> cost[tmp][1];
    }


    for(int gap=1; gap<m; gap++){
        for(int s=0; s<m; s++){
            int e = s + gap;
            if(e < m){
                if(str[s] == str[e]){
                    d[s][e] = d[s+1][e-1];
                }
                else{
                    int imin1 = ( cost[str[s]][0] < cost[str[s]][1] ? cost[str[s]][0] : cost[str[s]][1] );
                    d[s][e] = d[s+1][e] + imin1;

                    int imin2 = ( cost[str[e]][0] < cost[str[e]][1] ? cost[str[e]][0] : cost[str[e]][1] );

                    if(d[s][e] > d[s][e-1] + imin2)
                        d[s][e] = d[s][e-1] + imin2;
                }
            }
        }
    }

    cout << d[0][m-1] << endl;

    return 0;
}





相关阅读:
Top