牛客：小美的01串翻转

骑猪看日落 2024-03-03 07:13 11阅读 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 条评论，11人围观）

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

相关阅读

相关牛客小白月赛

[(0条未读通知) 牛客小白月赛78\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][0_ _78_ACM_N

朱雀/ 2024年03月03日 08:56/ 0 赞/ 71 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关最长公共子串（C++牛客网）

解题思路：（1）动态规划 class Solution { public: / longest common subs

柔情只为你懂/ 2022年11月17日 05:22/ 0 赞/ 169 阅读

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

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

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

相关【day01】组队竞赛_牛客网（贪心）

文章目录组队竞赛题目描述输入输出示例及描述解题思路及源码组队竞赛题目描述题目链接：[组队竞赛][

﹏ヽ暗。殇╰゛Y/ 2022年10月28日 04:57/ 0 赞/ 159 阅读

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

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

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

相关牛客网刷题纠错01

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

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