[NOIp2013] luogu P1970 花匠

scy居然开网了。

题目描述

Solution

后来一想这玩意貌似跟 DP 没什么关系。$n$ 只开到 1 0 5 10^5 105，有点心机。

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

#include
#include
#includeconst 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]));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！