[NOIp2013] luogu P1970 花匠

scy居然开网了。

题目描述

你有一个序列 aaa，你需要保留尽量多的数，使得剩下的数满足以下条件中的一个：

∀x∈[2,n−1]∩N∗\forall x\in[2,n-1]∩\N^*∀x∈[2,n−1]∩N∗ 有 ax−1<ax>ax+1a_{x-1}<a_x>a_{x+1}ax−1<ax>ax+1；
∀x∈[2,n−1]∩N∗\forall x\in[2,n-1]∩\N^*∀x∈[2,n−1]∩N∗ 有 ax−1>ax<ax+1a_{x-1}>a_x<a_{x+1}ax−1>ax<ax+1。

求保留的数量的最大值。

Solution

后来一想这玩意貌似跟 DP 没什么关系。nnn 只开到 10510^5105，有点心机。

设 f[i],g[i]f[i],g[i]f[i],g[i] 分别表示对于前 iii 位，选用条件一或条件二的结果。如果 a[i]<a[i−1]a[i]<a[i-1]a[i]<a[i−1]，则 f[i]f[i]f[i] 可能变得更优；如果 a[i]>a[i−1]a[i]>a[i-1]a[i]>a[i−1]，则 g[i]g[i]g[i] 可能变得更优。如果相等，则继承上一位的答案。时间复杂度 O(n)O(n)O(n)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

const int MAXN=100010;

int n;

int a[MAXN];

int f[MAXN],g[MAXN];

int max(int x,int y){

	return x>y?x:y;

}

int main(){

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	f[1]=g[1]=1;

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

		if(a[i]>a[i-1]){

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

			g[i]=g[i-1];

		}

		else if(a[i]<a[i-1]){

			f[i]=f[i-1];

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

		}

		else{

			f[i]=f[i-1];

			g[i]=g[i-1];

		}

	}

	printf("%d",max(f[n],g[n]));

}

巴特西

[NOIp2013] luogu P1970 花匠

题目描述

Solution

最新文章

热门文章