记录编号	441900	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2017-08-25 19:42:18	内存使用	2.22 MiB

#include<bits/stdc++.h>//整体思路还是蛮简单的，写了一小时a掉了，首先三十分暴力，2^n枚举判断
//80分就是n2写法，每个状态由前面所有状态转移而来
//100分时n写法，只枚举前一个状态 
using namespace std;
int n,a[100005],f[100005][2],F[100005][2];//f[i][0]表示到i可以放多少花，f[i][1]表示最后一盆花的位置 
int main()//f表示A，F表示B 
{
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	f[1][0]=1;
	f[1][1]=1;
	F[1][0]=1;
	F[1][1]=1;
	for(int i=2;i<=n;i++){
	//	for(int j=i;j>=1;j--){
			int j=i-1;
			if(f[j][0]&1){//可以放则放 ，i为偶数位 
				if(a[i]>a[f[j][1]]){
						f[i][0]=f[j][0]+1;
						f[i][1]=i;
				}
				else{
					if(a[i]<a[f[j][1]]){//不可以放，那么将前面的状态转移过来，如果当前位更优则替换反之则继承 
						f[i][1]=i;
						f[i][0]=f[j][0];
					}
					else{
						f[i][1]=f[j][1];
						f[i][0]=f[j][0];
					}
				}
			}
			else{//奇数位 
				if(a[i]<a[f[j][1]]){
						f[i][0]=f[j][0]+1;
						f[i][1]=i;
				}
				else{
					if(a[i]>a[f[j][1]]){
						f[i][1]=i;
						f[i][0]=f[j][0];
					}
					else{
						f[i][1]=f[j][1];
						f[i][0]=f[j][0];
					}
				}
			}
			if(F[j][0]&1){
				if(a[i]<a[F[j][1]]){
						F[i][0]=F[j][0]+1;
						F[i][1]=i;
				}
				else{
					if(a[i]>a[F[j][1]]){
						F[i][1]=i;
						F[i][0]=F[j][0];
					}
					else{
						F[i][1]=F[j][1];
						F[i][0]=F[j][0];
					}
				}
			}
			else{
				if(a[i]>a[F[j][1]]){
						F[i][0]=F[j][0]+1;
						F[i][1]=i;
				}
				else{
					if(a[i]<a[F[j][1]]){
						F[i][1]=i;
						F[i][0]=F[j][0];
					}
					else{
						F[i][1]=F[j][1];
						F[i][0]=F[j][0];
					}
				}
			}
	//	}
	}
	cout<<max(f[n][0],F[n][0]);
/*	int ma=-1;
	for(int i=1;i<=n;i++){
		ma=max(ma,max(F[i][0],f[i][0]));
	}
	cout<<ma;*/
	return 0;
}