花匠

2013noip day2 第二题，挺简单的dp

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 100000+10;

int n;

int a[maxn],f[maxn],g[maxn];

void init()

{

freopen("in.txt","r",stdin);

freopen("out.txt","w",stdout);

}

void readdata()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=1;i<=n;i++)

{

g[i]=1;

f[i]=1;

}

}

void work()

{

for(int i=2;i<=n;i++)

{

for(int j=i-1;j>0;j--)

{

if(a[j] > a[i])

{

f[i]=max(g[j]+1,f[i]);

}

if(a[j] == a[i])

{

f[i]=max(f[i],f[j]);

g[i]=max(g[i],g[j]);

}

if(a[j] < a[i])

{

g[i]=max(g[i],f[j]+1);

}

}

}

int m=1;

for(int i=1;i<=n;i++) m=max(m,max(f[i],g[i]));

printf("%d",m);

}

int main()

{

readdata();

work();

return 0;

}