1 条题解
-
0
#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
- 上传者