AcWing 1222. 密码脱落

2021-03-01 06:28

阅读：736

标签：-- desc rgba cstring ons 线性 www mem main

原题链接

考察:区间DP+线性dp

思路一:

正向求解,f[i][j]表示[i,j]区间内应该删去的字符数.要注意的是如果i>j,那么为不合法区间,设置f[i][j] = 0.i = j,单个字符一定回文,f[i][j] = 0.接下来就是划分集合:s[i]=s[j]可缩小到f[i+1,j-1].如果s[i]!=j,在f[i,j-1]与f[i+1,j]取最小值.(对应去掉左端点或去掉右端点的情况,都去的情况可被覆盖)

 1 #include  2 #include  3 #include  4 #include 
 5 using namespace std;
 6 const int N = 1010;
 7 char s[N];
 8 int f[N][N];
 9 int main()
10 {
11     scanf("%s",s+1);
12     int len = strlen(s+1);
13     memset(f,0x3f,sizeof f);
14     for(int i=0;i5;i++)
15       for(int j=0;j0;
16     for(int i=len;i>=1;i--)
17         for(int j=i;j)
18         {
19             if(s[i]==s[j]) f[i][j] = f[i+1][j-1];
20             else f[i][j] = min(f[i+1][j],f[i][j-1])+1;
21         }
22     printf("%d\n",f[1][len]);
23     return 0;
24 }

思路一

思路二:

逆向求解,f[i][j]表示[i,j]区间内最大的对称串长度.答案为串长度-回文串长度.

划分集合:如果l,r都在里面,f[i][j] = f[i+1][j-1]+2;l不在回文串内,r在,此情况存在条件是[l+1,r]内存在与r相等的字符.此情况太难求,可以考虑覆盖即f[l+1,r].同理l在r不在,都不在就是f[l+1,r-1].

注意:f[l]会用到f[l+1]所以需要l倒着推,也可以直接枚举区间长度.

AcWing 1222. 密码脱落

标签：-- desc rgba cstring ons 线性 www mem main

原文地址：https://www.cnblogs.com/newblg/p/14395919.html

上一篇：WSL安装流程 Windows下的linux

下一篇：Thread线程

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 1222. 密码脱落
文章链接：http://soscw.com/index.php/essay/58443.html

亲，登录后才可以留言！

AcWing 1222. 密码脱落

评论

热门文章

推荐文章

最新文章

置顶文章