P1410 子序列

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

转移方程：,显然这是对以结尾的子序列进行更新的，

所以直接取

当，这说明前位不以结尾长度为的子序列长度可以进行更新。

最后判断一下能否到达即可。

初始状态：.其他初始化为。因为前一个字符不为结尾的序列就是空序列必然存在。

#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;
}