牛客：小美的01串翻转

骑猪看日落 2024-03-03 07:13 33阅读 0赞

[小美的01串翻转][01]  
![在这里插入图片描述][ead0a3fb66d144059a73599e114a8cd2.png]

#include<iostream>
    #include<cstring>
    #include<string>
    #include<vector>
    
    using namespace std;
    typedef long long ll;
    const int N = 1100;
    string s;
    ll res = 0;
    
    int main()
    {
        
        cin>>s;
        
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(2));
        
         for (int i = 0; i < n; i++) 
         {
        
            for (int j = i; j < n; j++) 
            {
        
                if (j == i) 
                {
        
                    if (s[j] == '0') 
                    {
        
                        dp[j] = {
        0,1};
                    }
                    else
                    {
        
                        dp[j] = {
        1,0};
                    }
                }
                else
                {
        
                    if (s[j] == '0') 
                    {
        
                        dp[j][0] = dp[j-1][1];
                        dp[j][1] = dp[j-1][0] + 1;
                    }
                    else 
                    {
        
                        dp[j][0] = dp[j-1][1] + 1;
                        dp[j][1] = dp[j-1][0];
                    }
                }
                res += min(dp[j][0], dp[j][1]);
            }
        }
        cout << res << endl;
        
        return 0;
    }

[01]: https://ac.nowcoder.com/acm/contest/63869/C
[ead0a3fb66d144059a73599e114a8cd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/cc8a94e74bbf4e8abbe32045b2f6a93b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客：小美的01串翻转

[小美的01串翻转][01] ![在这里插入图片描述][ead0a3fb66d144059a73599e114a8cd2.png] include<iostrea

骑猪看日落/ 2024年03月03日 07:13/ 0 赞/ 34 阅读

相关牛客-小易的升级

题目描述小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2

墨蓝/ 2023年07月19日 10:55/ 0 赞/ 14 阅读

相关牛客最长公共子串问题

题目链接：[https://www.nowcoder.com/practice/210741385d37490c97446aa50874e62d?tpId=101&tqId=3

向右看齐/ 2023年06月04日 14:54/ 0 赞/ 23 阅读

相关牛客回文串

题目描述给定一个字符串，问是否能通过添加一个字母将其变为回文串输入描述 > 一行一个由小写字母构成的字符串，字符串长度小于等于10 输出描述 > 输出答案(Y

Dear 丶/ 2023年05月22日 11:28/ 0 赞/ 6 阅读

相关牛客小白月赛4-F-等价串题解

文章目录题目描述输入分析输出分析输入输出说明算法分析解题代码 --

你的名字/ 2022年12月28日 11:17/ 0 赞/ 159 阅读

相关牛客网题目翻转字串（python实现）

题目描述：假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，

一时失言乱红尘/ 2022年12月08日 15:45/ 0 赞/ 195 阅读

相关 01背包（C++牛客网）

解题思路：（1）动态规划 class Solution { public: / 代码中的类名、方法名、参数名已经指定，

╰半橙微兮°/ 2022年11月19日 04:23/ 0 赞/ 75 阅读

相关公共子串计算（C++牛客网）

解题思路：（1）动态规划 include<iostream> include<vector> using namespace std;

傷城~/ 2022年11月13日 04:01/ 0 赞/ 485 阅读

相关牛客题霸 NC28 最小覆盖子串

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac 解决方案 Go 版本一

痛定思痛。/ 2022年09月11日 04:09/ 0 赞/ 218 阅读

相关牛客网刷题纠错01

文章目录 1.for循环中的逗号表达式 2.printf输出使用%5.3s输出字符串 3.double类型的数据加int类型的数据 4.编程题的哈

缺乏、安全感/ 2021年12月12日 13:11/ 0 赞/ 341 阅读