A. A Twisty Movement dp

https://codeforces.com/problemset/problem/933/A

 

这个是一个dp，但是我并没有看出来，然后也不太会写，

这种题一般应该要想到先预处理前缀和后缀，然后再进行dp

dp[i][j][0]----表示从区间 i~j 以2结尾的最长递减序列 

dp[i][j][1]----表示从区间 i~j 以1结尾的最长递减序列

为什么这样定义，我很迷，完全不知道要这么写，?

dp[i][j][0]=dp[i][j-1][0]+(a[i]==2)

dp[i][j][1]=max(dp[i][j-1][0],dp[i][j-1][1]+(a[i]==1))

这个状态转移方程还是很好想的，如果是以2结尾的最长递减序列，那么状态转移就只有一种

如果是以1结尾的最长递减序列，可以是前面为2最后为1，也可以是一直是1。

 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
#define debug(x) cout<<"-----"<<" x = "<<x<<"-----"<<endl
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
ll dp[maxn][maxn][3];
int a[maxn];
ll pre[maxn], suf[maxn];
int main()
{
    int n;
    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);
    ll ans = 0;
    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);//代表以2结尾的最长的递减序列
            dp[i][j][1] = max(dp[i][j - 1][0], dp[i][j - 1][1]) + (a[j] == 1);//代表以1结尾的最长的递减序列

            ans = max(ans, pre[i - 1] + dp[i][j][0] + suf[j + 1]);
            ans = max(ans, pre[i - 1] + dp[i][j][1] + suf[j + 1]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}