bzoj 1236: longpo的回文

1236: longpo的回文

题目描述

一个字符串如果从左到右和从右到左读的结果是一样的，我们称之为回文串。现在给定一个字符串，我们有三种操作：

1. 添加一个字母在任何位置(可以在首尾添加) (add ‘*’)

2. 删除一个字母 (erase ‘*’)

3. 改变一个字母变成另外一个字母 (change ‘*’ to ‘*’)

然而，这些操作可以改变的字母是由longpo指定的。比如，longpo指定可以删除字母’a’，添加字母’b’，改变字母’d’。没指定的操作其他的字母不可以改变。

另外，每个操作需要有代价，因此，这三个操作可以描述为：

1. “add c x”

2. “erase c x”

3. “change c1 c2 x”

分别表示增加字母c需要x的代价，删除字母c需要x的代价，改变c1变成c2需要x的代价。

现在给你一个字符串，然后n个操作，问你最少需要多少代价将这个字符串变成回文串，输出最小代价。如果不能变成回文串，则输出”-1”。

输入

输入一个长度为m的字符串，全部由小写字母组成(‘a’-‘z’)。

输入操作数量n，然后输入n个操作。

输出

输出最小代价，如果不能变成回文串，则输出”-1”。

样例输入

topcoder

7

erase t 1

erase o 1

erase p 1

erase c 1

erase d 1

erase e 1

erase r 1

样例输出

样例2

caaaaaab

change b a 100000

change c a 100000

change c d 50000

change b e 50000

erase d 50000

erase e 49999

样例2

199999

数据范围：

30%数据 1<=m<=10, 1<=n<=10

100%数据 1<=m<=50, 1<=n<=50, 1<=x<=100000

题解：

神题啊！！！

这题确实不错，dp+大量的分类讨论（情况其实不多，但确实难想）。。

pre[i]表示把i这个字符消掉的最小代价，那么有5种情况：

1.添加一个一样的字符

2.直接删除它

3.添加一个字符，再把这个字符变成它

4.把它变成某个字符再删除它

5.把它变成某个字符，再添加一个字符并让这个字符改变成一样的

由于涉及到字符的变化，所以先用floyd预处理出（这里是单向的），这里用Pre[i][j]记录。

接下来就是裸的DP了，

f[i][j]=f[i+1][j-1] (a[i]==a[j])

f[i][j]=min{f[i+1][j]+pre[a[i]],f[i][j-1]+pre[a[j]],f[i+1][j-1]+Pre[a[i]][a[j]]}

但是这样还是不够，我们还是漏了一种情况，也就是a[i],a[j]同时变化到某一个字符，枚举一下好了，数据还是很仁慈的。

#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

const int N=55;

char a[N],b[10],c[2],d[2];

int n,m,i,j,k,x,y;

long long f[N][N],preA[30],pre[30],preE[30],Pre[30][30];

inline void read(int &v){

    char ch,fu=0;

    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());

    if(ch=='-') fu=1, ch=getchar();

    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';

    if(fu) v=-v;

}

int main()

{

    scanf("%s",a+1);

    n=strlen(a+1);

    read(m);

    for(i=0;i<=26;i++) pre[i]=preA[i]=preE[i]=1e14;

    for(i=0;i<=26;i++)

     for(j=0;j<=26;j++) Pre[i][j]=1e14;

    for(i=1;i<=m;i++)

    {

        scanf("%s%s",b,c);

        if(b[0]=='a')

        {

            read(x);

            preA[c[0]-'a']=min(preA[c[0]-'a'],(long long)x);

        } else

        if(b[0]=='e')

        {

            read(x);

            preE[c[0]-'a']=min(preE[c[0]-'a'],(long long)x);

        } else

        {

            scanf("%s",d);

            read(x);

            Pre[c[0]-'a'][d[0]-'a']=min(Pre[c[0]-'a'][d[0]-'a'],(long long)x);

        }

    }

    for(k=0;k<26;k++)

     for(i=0;i<26;i++)

      for(j=0;j<26;j++)

      Pre[i][j]=min(Pre[i][j],Pre[i][k]+Pre[k][j]);

    for(i=0;i<26;i++)

     for(j=0;j<26;j++)

    {

        pre[i]=min(pre[i],min(preA[i],preE[i]));

        pre[i]=min(pre[i],Pre[i][j]+min(preE[j],preA[j]));

        pre[i]=min(pre[i],preA[j]+Pre[j][i]);

        for(k=0;k<26;k++)

            pre[i]=min(pre[i],Pre[i][j]+preA[k]+Pre[k][j]);

    }

    for(i=n;i>=1;i--)

     for(j=i+1;j<=n;j++)

    {

        f[i][j]=1e14;

        if(a[i]==a[j]) f[i][j]=f[i+1][j-1];

        f[i][j]=min(f[i][j],f[i+1][j]+pre[a[i]-'a']);

        f[i][j]=min(f[i][j],f[i][j-1]+pre[a[j]-'a']);

        f[i][j]=min(f[i][j],f[i+1][j-1]+min(Pre[a[j]-'a'][a[i]-'a'],Pre[a[i]-'a'][a[j]-'a']));

        for(k=0;k<26;k++)

            f[i][j]=min(f[i][j],f[i+1][j-1]+Pre[a[i]-'a'][k]+Pre[a[j]-'a'][k]);

    }

    if(f[1][n]==1e14) cout<<"-1";else cout<<f[1][n];

}

巴特西

bzoj 1236: longpo的回文

1236: longpo的回文

题目描述

输入

输出

样例输入

样例输出

最新文章

热门文章