Mxnet 微服务 volatile 反射 postgresql reflection vue教程 pmp培训视频 jquery获取dom对象 flutter项目案例 mysqlinsert python输出函数 python中len函数 python传递参数 java如何连接mysql javapattern java的方法 java基本数据结构 java获取数据类型 java中random java删除数组中的某个元素 java绝对值 linux密码 din字体 saminside 美国地址生成器 苹果放大镜 ps去白底 ipad怎么清理内存垃圾 网易云听歌识曲电脑版 ppt背景音乐怎么关 class选择器 视频下载高手 安装telnet 恶意软件清理 战地4配置 方正兰亭粗黑简体 迅捷cad转换器 声音测试软件 mysql注释
当前位置: 首页 > 学习教程  > 编程语言

Codeforces603 A.Alternative Thinking(dp)

2020/12/5 10:26:25 文章标签:

题意&#xff1a; 数据范围&#xff1a;|串|<1e5 解法&#xff1a; d[i][0]表示第i位不修改能取得的最大值. d[i][1]表示第i位不修改,但是前面存在修改能取得的最大值. d[i][2]表示第i位修改能取得的最大值.d[i][0]可以由d[i-1][0]转移, d[i][1]可以由d[i-1][1],d[i-1][2]…

题意:

在这里插入图片描述
数据范围:|串|<=1e5

解法:

d[i][0]表示第i位不修改能取得的最大值.
d[i][1]表示第i位不修改,但是前面存在修改能取得的最大值.
d[i][2]表示第i位修改能取得的最大值.

d[i][0]可以由d[i-1][0]转移,
d[i][1]可以由d[i-1][1],d[i-1][2]转移,
d[i][2]可以由d[i-1][2],d[i-1][0]转移,

code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e6+5;
int d[maxm][3];
char s[maxm];
int n;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    cin>>(s+1);
    d[1][0]=d[1][1]=d[1][2]=1;
    for(int i=2;i<=n;i++){
        //d[i][0]表示第i位不修改能取得的最大值.
        d[i][0]=d[i-1][0]+(s[i]!=s[i-1]);
        //d[i][1]表示第i位不修改,但是前面存在修改能取得的最大值.
        d[i][1]=d[i-1][1]+(s[i]!=s[i-1]);
        d[i][1]=max(d[i][1],d[i-1][2]+(s[i]==s[i-1]));
        //d[i][2]表示第i位修改能取得的最大值.
        d[i][2]=d[i-1][2]+(s[i]!=s[i-1]);
        d[i][2]=max(d[i][2],d[i-1][0]+(s[i]==s[i-1]));
    }
    cout<<max(d[n][0],max(d[n][1],d[n][2]));
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_450234.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?