题目描述
小Z有一个01序列A=(A1,A2,A3,…,An)。他可以进行一次操作：选择一个区间L,R将其反转。
例如，对于序列A=(1,0,0,1,1)，当L=2,R=4时，原序列将变为(1,1,0,0,1)。
小Z希望：通过这一次反转操作，使得这个序列的最长不下降子序列的长度尽可能的大，并想让你输出这个最大值。
一个序列的不下降子序列定义为：对于一个序列(p1,p2,…,pk)满足1≤p1<p2<…<pk≤n(n≤819200)且Ap1≤Ap2≤…≤Apk。则序列(Ap1,Ap2,…,Apk)为不下降子序列，其中k为这个不下降子序列的长度。
输入
一行一个01字符串，表示序列A
输出
一行一个正整数，表示最长不下降子序列长度的最大值。
样例输入
00111001101
样例输出
10
提示
一种最优策略为：反转区间[3,7]，数列将变为(0,0,0,0,1,1,1,1,1,0,1) ，其最长不下降子序列的长度为10。
在一开始的时候以为反转某一段区间之后，只会影响反转的这一块中0或1的数量与前一段或后一段的0或1的数量
然后统计出来0或1的块的大小，只反转1…10…0这样的区间，其实是错的
答案会影响四段
wrong_code:
记录反转了这一块后前面0的个数与后面1的数量思路其实是错的
int n,k; int a[maxn]; struct node{ int id; int ct; }b[maxn]; int main() { string s; cin >> s; n = s.size(); s = "#" + s; int cnt = 0; int t = 0; int bak1 = 0; for(int i=1;i<=n;i++){ ++ t; if(i == n || s[i] != s[i+1]){ b[++cnt].id = s[i] - '0'; b[cnt].ct = t; t = 0; if(s[i] == '1') bak1 += b[cnt].ct; } } /*for(int i=1;i<=cnt;i++){ cout << b[i].id<<' '<<b[i].ct<<endl; }*/ /// debug(bak1); if(cnt == 1 || cnt == 2){ cout << n <<endl; return 0; } int pre0 = 0; int ans = 0; b[0].id = 0,b[0].ct=0; for(int i=1;i<cnt;i++){ if(b[i-1].id == 0) pre0 += b[i-1].ct; else bak1 -= b[i-1].ct; ans = max(ans,bak1 + pre0); if(b[i].id == 1 && b[i+1].id == 0){ ans = max(ans,pre0 + b[i+1].ct + bak1); /*debug(pre0); debug(b[i+1].ct); debug(bak1);*/ // cout << pre0 + b[i+1].ct + bak1 <<endl; } } cout << ans <<endl; return 0; } /************************************************************** Problem: 13769 Language: C++ Result: 答案错误 ****************************************************************/
ac_code:
int main() { string s; cin >> s; n = s.size(); s = "#" + s; int t1,t2,t3,res; t1 = t2 = t3 = res = 0; for(int i=1;i<=n;i++){ if(s[i] == '0'){ ++ t1; t2 = max(t1,t2); t3 = max(t2,t3 + 1); res = max(res,t3); }else{ t2 = max(t1,t2 + 1); t3 = max(t2,t3); res = max(t3,res + 1); } } cout << res <<endl; return 0; } /************************************************************** Problem: 13769 Language: C++ Result: 正确 Time:40 ms Memory:15588 kb ****************************************************************/
追更：
其实这道题和acwing上面，这道题是一样的
应该考虑答案影响的四段
最优质一定是在00000111110000011111
这种情况下的
我们用s1记录00000的最长长度
用s2 记录0000011111的最长长度
用s3 记录000001111100000的最长长度
用s4 记录00000111110000011111的最长长度
最终答案就是s3,s4中最大值
O(n)
该题code:
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { int n; cin >> n; int s1 = 0,s2 = 0,s3 = 0,s4 = 0; for(int i=1;i<=n;i++){ int x;scanf("%d",&x); if(x == 1){ ++ s1; s3 = max(s2 + 1,s3 + 1); }else{ s2 = max(s1 + 1,s2 + 1); s4 = max(s3 + 1,s4 + 1); } } cout << max(s3,s4) <<endl; return 0; }
