longpo的回文

啊...比赛的时候输入打错了，结束之后还照着题解把DP部分重构了一遍然而还是WA...样例都没过，然后直接输了-1

明显的DP...而且数据范围这么小，显然怎么搞都可以...

而且这样的回文的DP是很经典的DP啊

f[i][j]表示从i到j所需要最少的价格

$$f[i][j]=\begin{cases}f[i+1][j-1]&& \text{s[i]=s[j]}\\min\{f[i+1][j]+cst[s[i]],f[i][j-1]+cst[a[j]],f[i+1][j-1]+dis[a[i]][a[j]]\}&& \text{}\end{cases}$$

其中cst[i]，dis[i][j]分别表示把i消掉（变成回文）和把i变成j所要的最小代价

有点恶心的是...add erase change可以组合起来形成新的操作

比如说change a->b等价于erase a再add b,显然我们要进行分类讨论

不难发现有这些情况：

$$\begin{cases}把a删掉再加上b& \text{}\\加上a再换成b&& \text{}\\把a变成b再删掉 &&\text{}\\在a后面再加一个a &&\text{}\\直接删掉a &&\text{}\end{cases}$$

而且这些操作互相之间是有联系的...所以操作顺序要改一下

然后因为可能会有a->b->c->d之类的路径存在，我们可以跑Floyd来求得最终的dis[i][j]

然后就可以愉快的DP了，注意填表顺序(有点像区间DP)...

#include<cstdio>

#include<queue>

#include<iostream>

#include<cstring>

#define int long long

using namespace std;

inline int read(){

    int ans=,f=;char chr=getchar();

    while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

    while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

    return ans*f;

}int n,m,dis[][],era[],add[],f[][],cst[];

char s[],opt[],kk[],ccc[];

signed main(){//比赛的时候读入读错了...自闭

    scanf("%s",s+);

    for(register int i=;i<=;i++) cst[i]=add[i]=era[i]=1e14;

    for(register int i=;i<=;i++) for(int j=;j<=;j++)dis[i][j]=1e14;

    n=strlen(s+);m=read();

    for(register int i=,x;i<=m;++i){

        scanf("%s%s",opt,kk);

        if(opt[]=='c'){

            scanf("%s",ccc);

            x=read();

            dis[kk[]][ccc[]]=min(x,dis[kk[]][ccc[]]);

        }else if(opt[]=='e'){

            x=read();

            era[kk[]]=min(era[kk[]],x);

        }else{

            x=read();

            add[kk[]]=min(add[kk[]],x);

        }

    }

    for(register int i='a';i<='z';i++) dis[i][i]=;

    for(register int k='a';k<='z';k++)

        for(register int i='a';i<='z';i++)

            for(register int j='a';j<='z';j++)

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

    for(register int i='a';i<='z';i++)

        for(register int j='a';j<='z';++j){

        cst[i]=min(cst[i],min(add[i],era[i])),

        cst[i]=min(cst[i],dis[i][j]+min(era[j],add[j])),

        cst[i]=min(cst[i],add[j]+dis[j][i]);

        for(register int k='a';k<='z';++k)

            cst[i]=min(cst[i],dis[i][j]+add[k]+dis[k][j]);

    }

    for(register int i=n;i>=;i--){

        for(register int j=i+;j<=n;++j){f[i][j]=1e14;

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

            f[i][j]=min(f[i][j],f[i+][j]+cst[s[i]]);

            f[i][j]=min(f[i][j],f[i][j-]+cst[s[j]]);

            f[i][j]=min(f[i][j],f[i+][j-]+min(dis[s[j]][s[i]],dis[s[i]][s[j]]));

            for(int k='a';k<='z';++k)

                f[i][j]=min(f[i][j],f[i+][j-]+dis[s[i]][k]+dis[s[j]][k]);

        }

    }

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

    return ;

}

巴特西

longpo的回文

最新文章

热门文章