Codeforces 934C - A Twisty Movement (dp)

原题地址:http://codeforces.com/contest/934/problem/C

题意:给定一个长度不超过2000的由1和2组成的字符串$S$，可以选定一个区间$[l, r]$，将S的子串$Si...Sj$做一次$reverse$操作（变成$Sj..Si$），问怎么选定区间，使得的到的新串的最长非严格递增序列的长度最长。并输出其长度。

思路:很容易想到要预处理出1的前缀和$pre[i]$和2的后缀和$suf[i]$
然后枚举区间，对于每个区间如果能求出最长递减序列的长度，那么就能更新答案了
这个用dp求状态：

dp[i][j][0]表示i–j区间以2结尾的最长递减序列长度，很明显这个序列全为2，所以也就是i–j区间2的个数
dp[i][j][1]表示i–j区间以1结尾的最长递减序列长度
状态转移：
$dp[i][j][0]=dp[i][j-1][0]+(a[j]==2)$
$dp[i][j][1]=max(dp[i][j-1][0],dp[i][j-1][1])+(a[j]==1)$

#include <bits/stdc++.h>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)+1
#define CLR(x,y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 2000 + 5;
const int mod = 998244353;
int n, a[maxn];
int pre[maxn], suf[maxn];
int dp[maxn][maxn][3];//dp[i][j][k]表示在区间[i,j]内,以数字k结尾的最长不上升子序列
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (a[i] == 1);
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + (a[i] == 2);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dp[i][j][0] = dp[i][j - 1][0] + (a[j] == 2);
            dp[i][j][1] = max(dp[i][j - 1][0], dp[i][j - 1][1]) + (a[j] == 1);
        }
    }
    int MAX = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            MAX = max(MAX, pre[i - 1] + suf[j + 1] + dp[i][j][0]);
            MAX = max(MAX, pre[i - 1] + suf[j + 1] + dp[i][j][1]);
        }
    }
    printf("%d\n", MAX);
    return 0;
}