锐客网

  1. 首页 > 睿知 > it技术 > >

bzoj 1710: [Usaco2007 Open]Cheappal 廉价回文区间dp

IT知识区间DP回文

但使书种多，会有岁稔时。这篇文章主要讲述bzoj 1710: [Usaco2007 Open]Cheappal 廉价回文区间dp相关的知识，希望能为你提供帮助。
【bzoj 1710: [Usaco2007 Open]Cheappal 廉价回文区间dp】只要发现添加一个字符和删除一个字符是等价的，就是挺裸的区间dp了
因为在当前位置加上一个字符x就相当于在他的对称位置删掉字符x，所以只要考虑删除即可，删除费用是添加和删除取min
设f[i][j]为从i到j的价格，长度从小到大枚举更新就行了 f[i][j]=min(f[i][j-1]+cost[s[j]],f[i+1][j]+cost[s[i]])，如果s[i]==s[j]还能和f[i+1][j-1]取个min
cpp #include< iostream> #include< cstdio> using namespace std; const int N=2005; int m,n,a[30],f[N][N],x,y; char s[N],ch[10]; int main() {scanf("%d%d",& m,& n); scanf("%s",s+1); for(int i=1; i< =m; i++){scanf("%s%d%d",ch,& x,& y); a[ch[0]-‘a‘]=min(x,y); }for(int i=1; i< =n; i++)s[i]-=‘a‘,f[i][i]=0,f[i+1][i]=0; for(int l=1; l< =n; l++)for(int i=1; i+l< =n; i++){int j=i+l; f[i][j]=min(f[i][j-1]+a[s[j]],f[i+1][j]+a[s[i]]); if(s[i]==s[j])f[i][j]=min(f[i][j],f[i+1][j-1]); }printf("%d\n",f[1][n]); return 0; } /* 3 4 abcb a 1000 1100 b 350 700 c 200 800 */




    推荐阅读


    上一篇：Spring MVC之HandlerMapping初始化

    下一篇：Win 8系统开机后按键盘出现蓝屏bad pool caller的处理办法