P1410 子序列

思路：看到 $n$ 最大是 $2000$ 。就应该想到用 $dp$ 写写。根据别人大佬的思路，我再来说说。。。首先我们可以假设 $dp[i][j]$ 为前 $i$ 位以 $a[i]$ 结尾子序列长度为 $j$ 是否满足。但是我们用这一个递推是不能判断另外一个子序列是否满足的，因此我们需要用 $dp[i][j]$ 来表示前 $i$ 位不以 $a[i]$ 结尾长度为 $i-j$ 的最后一位的最小值(根据贪心越小越有利后面的数)。这样就可以同时对两个子序列进行转移。

转移方程： $a[i+1]>a[i]$ ,显然这是对以 $a[i]$ 结尾的子序列进行更新的，

所以 $dp[i+1][j+1]$ 直接取 $min(dp[i+1][j+1],dp[i][j])$

当 $a[i+1]>dp[i][j]$ ，这说明前 $i$ 位不以 $a[i]$ 结尾长度为 $i-j$ 的子序列长度可以进行更新。

$dp[i+1][i-j+1]=min(dp[i+1][i-j+1],a[i])$

最后判断一下 $dp[n][\dfrac{n}{2}]$ 能否到达即可。

初始状态： $dp[1][1]=-1$ .其他初始化为 $inf$ 。因为前一个字符不为 $a[1]$ 结尾的序列就是空序列必然存在。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5,inf=0x3f3f3f3f;
#define mst(a) memset(a,0,sizeof a)
int dp[N][N],a[N];
int main(){
    int n; 
    while(~scanf("%d",&n)){
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            memset(dp,0x3f,sizeof dp);
            dp[1][1]=-1;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=i;j++)
                    if(dp[i][j]!=inf){ //注意剪枝 
                if(a[i+1]>a[i]) dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
                if(a[i+1]>dp[i][j]) dp[i+1][i-j+1]=min(dp[i+1][i-j+1],a[i]);
                }
            if(dp[n][n/2]!=inf) puts("Yes!");
            else puts("No!");
        }
    return 0;
}