请选择 进入手机版 | 继续访问电脑版

Codeforces1466 C. Canine poetry(dp)

[复制链接]
林雨宣 发表于 2021-1-2 19:43:49 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题意:

给定长度为n的小写字母串S,问最少修改多少个字符,
能使得S不存在长度>1的回文串。

数据范围:n1的回文即不存在长度=2和长度=3的回文串.思量令dp[j][k]为前i个字符,后两个字符为j,k所需要的最小代价,但是这样复杂度似乎炸了,不可行.因为字符集为26,我们只需要查抄长度为2大概3的回文,发现我们并不需要知道后两个字符到底是什么,只需要知道他们是否被修改,因此令d[j][k],表现前i个字符,后两个字符的被修改状态分别为j和k,由于状态数较少,复杂度就降下去了.[/code] code:

[code]#include using namespace std;const int maxm=2e6+5;int d[maxm][2][2];char s[maxm];int a[maxm];int n;signed main(){    int T;cin>>T;    while(T--){        cin>>(s+1);        n=strlen(s+1);        if(n==1){            cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )