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=0,f=1;char chr=getchar(); while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} return ans*f; }int n,m,dis[500][500],era[500],add[500],f[505][505],cst[505]; char s[500],opt[20],kk[20],ccc[20]; signed main(){//比赛的时候读入读错了...自闭 scanf("%s",s+1); for(register int i=0;i<=499;i++) cst[i]=add[i]=era[i]=1e14; for(register int i=0;i<=499;i++) for(int j=0;j<=499;j++)dis[i][j]=1e14; n=strlen(s+1);m=read(); for(register int i=1,x;i<=m;++i){ scanf("%s%s",opt,kk); if(opt[0]=='c'){ scanf("%s",ccc); x=read(); dis[kk[0]][ccc[0]]=min(x,dis[kk[0]][ccc[0]]); }else if(opt[0]=='e'){ x=read(); era[kk[0]]=min(era[kk[0]],x); }else{ x=read(); add[kk[0]]=min(add[kk[0]],x); } } for(register int i='a';i<='z';i++) dis[i][i]=1; 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>=1;i--){ for(register int j=i+1;j<=n;++j){f[i][j]=1e14; if(s[i]==s[j]) f[i][j]=f[i+1][j-1]; f[i][j]=min(f[i][j],f[i+1][j]+cst[s[i]]); f[i][j]=min(f[i][j],f[i][j-1]+cst[s[j]]); f[i][j]=min(f[i][j],f[i+1][j-1]+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+1][j-1]+dis[s[i]][k]+dis[s[j]][k]); } } if(f[1][n]==1e14) cout<<-1;else cout<<f[1][n]; return 0; }
华为成长空间 480人发布