1 条题解

  • 0
    @ 2026-1-27 19:30:40
    #include<bits/stdc++.h>
    using namespace std;
    
    int dp[100100]={};  // [1] dp数组:dp[i]表示处理到第i个字符时,使前i+1个字符单调不降的最少操作次数
    
    int main(){
        int n;
        cin>>n;
        string s;
        cin>>s;
        int sum=0,flag=1;  // [2] sum-未使用;flag-状态标记:1表示当前序列仍处于“可自然递增”阶段,0表示已出现下降对,进入强制处理阶段
        
        for(int i=0;i<n;i++){
            // 计算当前字符的实际值:原字符 + 之前的翻转次数(奇数次翻转会改变字符,偶数次不变),模2后转回字符
            // 注:i=0时dp[i-1]为dp[-1],代码中默认其值为0(初始无翻转)
            s[i]=(( (s[i]-'0') + dp[i-1]%2 ) %2)%2+'0';
            
            if(flag==1){
                // 阶段1:序列仍可自然递增,未出现"10"下降对
                if(i == n-1) {
                    // 处理最后一个字符,无后续字符,无需操作
                    dp[i] = dp[i-1];
                    break;
                }
                if(s[i]==s[i+1]){
                    // 当前字符与下一个字符相同,无需操作
                    dp[i] = dp[i-1];
                }else if(s[i]=='0' && s[i+1]=='1'){
                    // 当前字符是0,下一个是1,序列递增,无需操作
                    dp[i] = dp[i-1];
                }else {
                    // 当前字符是1,下一个是0,出现"10"下降对,需要翻转1次
                    dp[i] = dp[i-1]+1;
                    flag=0;  // 进入阶段2:后续需要强制处理
                }
            }else{
                // 阶段2:已出现下降对,需保证后续字符单调不降(只能全0或全1,此处逻辑为后续不能出现0)
                if(s[i]=='0'){
                    // 当前字符是0,需要翻转1次使其变为1,保证序列递增
                    dp[i] = dp[i-1]+1;
                }else{
                    // 当前字符是1,无需操作
                    dp[i] = dp[i-1];
                }
            }
        }
        
        cout<<dp[n-1];  // [3] 输出处理完所有字符后的最少操作次数
        return 0;
    }
    
    • 1

    信息

    ID
    1401
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者