AcWing 3549. 最长非递减子序列
原题链接
困难
作者:
静静在Coding
,
2022-03-27 10:51:44
,
所有人可见
,
阅读 177
题解
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10000010;
int f[N][5];
// 状态1: 只能由状态1转移
// 状态2: 由状态1和状态2转移
// 状态3:由状态2和状态3转移
// 状态4:由状态3和状态4转移
int main()
{
int n;
cin>>n;
for(int i = 1;i <= n;i++){
int x;
scanf("%d",&x);
f[i][1] = f[i - 1][1] + (x == 1);
f[i][2] = max(f[i - 1][1],f[i - 1][2]) + (x == 2);
f[i][3] = max(f[i - 1][3],f[i - 1][2]) + (x == 1);
f[i][4] = max(f[i - 1][3],f[i - 1][4]) + (x == 2);
}
int res = 0;
for(int i = 1;i <= 4;i++) res = max(res,f[n][i]);
cout<<res;
return 0;
}