CF933A A Twisty Movement 题解
hmh100211
·
·
题解
题目传送门
题外话：
本蒟蒻基本不会 dp，所以写篇题解巩固下
题意分析：
题意很简单，给定一个长度为 n 的序列 a ，可以翻转一个区间的数，求翻转后的序列的最长不下降子序列的长度。
这题的数据范围要注意一下:
n \le 2000,1 \le a_i \le 2
那么很显然，一个位置的最长不下降子序列只有四种情况：
- 以 $ 1 $ 结尾，未翻转。
- 以 $ 2 $ 结尾，未翻转。
- 以 $ 1 $ 结尾，已翻转。
- 以 $ 2 $ 结尾，已翻转。
## 思路：
因为只有四种情况，所以定义一个二维数组 `dp` 来储存，$ dp_{i,j} $ 表示前 $ i $ 个数最长不下降子序列的第 $ j $ 种情况。
那么就可以推出状态转移方程了：
以 $ 1 $ 结尾，未翻转：
$$ dp_{i,0}=dp_{i-1,0}+(a_i=1) $$
以 $ 2 $ 结尾，未翻转：
$$ dp_{i,1}=\max(dp_{i,0},dp_{i-1,1}+(a_i=2)) $$
以 $ 1 $ 结尾，已翻转：
$$ dp_{i,2}=\max(dp_{i,1},dp_{i-1,2}+(a_i=1)) $$
以 $ 2 $ 结尾，已翻转：
$$ dp_{i,3}=\max(dp_{i,2},dp_{i-1,3}+(a_i=2)) $$
题目要求的是翻转后的序列的最长不下降子序列的长度，很显然，以 $ 2 $ 结尾的最长不下降子序列一定比以 $ 1 $ 结尾的最长不下降子序列长，那么最终结果就是 $dp_{n,3}$。
# AC Code：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[2222],dp[2222][5];
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//上面这段不用管
cin>>n; //读入a序列长度
for(int i=1;i<=n;i++){
cin>>a[i]; //读入a序列
}
for(int i=1;i<=n;i++){ //根据方程状态转移 ，注意下标从1开始，避免数组越界
dp[i][0]=dp[i-1][0]+(a[i]==1);
dp[i][1]=max(dp[i][0],dp[i-1][1]+(a[i]==2));
dp[i][2]=max(dp[i][1],dp[i-1][2]+(a[i]==1));
dp[i][3]=max(dp[i][2],dp[i-1][3]+(a[i]==2));
}
cout<<dp[n][3]; //输出答案
return 0;
}
```
# [AC](https://www.luogu.com.cn/record/118547831)