NOIP2013花匠

2013年11月11日8,3788

描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数ℎ₁, ℎ₂, … , ℎ_n。设当一部分花被移走后，剩下的花的高度依次为g₁, g₂, … , g_m，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有的1 ≤ i ≤ m/2，g_2i > g_2i−1，且g_2i > g_2i+1；

条件 B：对于所有的1 ≤ i ≤ m/2，g_2i < g_2i−1，且g_2i < g_2i+1。

注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入

输入的第一行包含一个整数，表示开始时花的株数。
第二行包含个整数，依次为ℎ1, ℎ2,… , ℎn，表示每株花的高度。

输出

输出一行，包含一个整数m，表示最多能留在原地的花的株数。

样例

输入数据

5 
5 3 2 1 2

1 2	5 5 3 2 1 2

输出数据

3

备注

「输入输出样例说明」

有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。

「数据范围」

对于 20%的数据，n ≤ 10；

对于 30%的数据，n ≤ 25；

对于 70%的数据，n ≤ 1000，0 ≤ ℎi≤ 1000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ ℎi≤ 1,000,000，所有的ℎi随机生成，所有随机数服从某区间内的均匀分布。

正解似乎是算拐点+1

数据随机dp水过

代码

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int a[100001];
int f[100001][2];//0要求比它大，1要求比它小
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		f[i][1]=f[i][0]=1;
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=i-1;j>0;j--)
		{
			if(a[j]>a[i])f[i][0]=max(f[j][1]+1,f[i][0]);
			if(a[j]<a[i])f[i][1]=max(f[j][0]+1,f[i][1]);
			if(f[i][0]!=1&&f[i][1]!=1)break;
		}
	cout<<max(f[n][0],f[n][1]);
	return 0;
}

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

int a[100001];

int f[100001][2];//0要求比它大，1要求比它小

int n;

int main()

{

cin>>n;

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

{

f[i][1]=f[i][0]=1;

cin>>a[i];

}

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

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

{

if(a[j]>a[i])f[i][0]=max(f[j][1]+1,f[i][0]);

if(a[j]<a[i])f[i][1]=max(f[j][0]+1,f[i][1]);

if(f[i][0]!=1&&f[i][1]!=1)break;

}

cout<<max(f[n][0],f[n][1]);

return 0;

}

« 最大连续子段和问题打水漂 »

ygy

正解各种O（n）吧？
#include <cstdio>
int s,n,k,i,a,b;
int main()
{
scanf("%d%d",&n,&a);
for(i=1;i<n;++i)
{
scanf("%d",&b);
if(b>a&&k!=1)k=1,s++;
if(b<a&&k!=2)k=2,s++;
a=b;
}
printf("%d",s+1);
}