解题报告:

如题,很水的题目,比背包还弱智的DP。直接上码~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iomanip>
#include<queue>
#include<map> 
#include<cstdlib>
#include<ctime>
#define ll long long
using namespace std;
inline ll read()
{
    ll s=0,k=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')k*=-1; 
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=(s<<3)+(s<<1)+c-'0';
        c=getchar();
    }
    return s*k;
}
void write(ll x)
{
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
ll n,a[2001],d[2001],x[2001],answer=0;
int main()
{
    n=read();
    for(ll i=1;i<=n;i++)
    {
        a[i]=read();
        d[i]=x[i]=1;
        for(ll j=1;j<i;j++)
        {
            if(a[j]>a[i])
            {
                d[i]=max(d[i],x[j]+1);
            }
            if(a[j]<a[i])
            {
                x[i]=max(x[i],d[j]+1);
            }
        }
        answer=max(answer,d[i]);
        answer=max(answer,x[i]);
    }
    write(answer);
}