【NOIP2013提高组】花匠
NOIP2013 提高组 Day2 试题。
题目描述花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数 h1, h2,… ,hn 。设当一部分花被移走后，剩下的花的高度依次为 g1,g2,...,gm，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的1≤i≤m/2,有 g2i>g2i-1，同时对于所有的 1≤i≤m/2,有 g2i>g2i+1；
条件 B：对于所有的1≤i≤m/2,有 g2i< g2i-1，同时对于所有的 1≤i≤m/2,有 g2i<g2i+1；
注意上面两个条件在 m=1 时同时满足，当 m>1 时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
输入格式输入的第一行包含一个整数 n，表示开始时花的株数。
第二行包含 n 个整数，依次为 h1, h2,…,hn ，表示每株花的高度。
输出一行，包含一个整数 m，表示最多能留在原地的花的株数。
样例数据 1输入
55 3 2 1 2
输出
3 备注【样例说明】
有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。
【数据范围】
对于 20% 的数据，n≤10；
对于 30% 的数据，n≤25；
对于 70% 的数据，n≤1000，0≤hi≤1000；
对于100% 的数据，1 ≤n≤ 100,000，0≤hi≤1,000,000，所有的 hi 随机生成，所有随机数服从某区间内的均匀分布。
【考试现场的题目更正】
为进一步明确题意，《花匠》一题中的条件 A 和条件 B 的补充说明如下：
解析：
原题可转化成求最长抖动序列。
令f[i][0/1]" role="presentation">f[i][0/1]表示到处理到i" role="presentation">i结尾为降/升的最大长度。
代码：
#include <bits/stdc++.h>
using namespace std;
const int Max=100005;
int n,m,l,r,mid,ans;
int f[Max][2],num[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void solve()
{
f[1][1]=f[1][0]=1;
for(int i=2;i<=n;i++)
{
f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
if(num[i-1]>num[i]) f[i][0]=max(f[i-1][1]+1,f[i][0]);
if(num[i-1]<num[i]) f[i][1]=max(f[i-1][0]+1,f[i][1]);
}
}
int main()
{
n=get_int();
for(int i=1;i<=n;i++) num[i]=get_int();
solve();
cout<<max(f[n][0],f[n][1]);
return 0;
}
相关知识
花匠鲜花加盟
“花匠”
花匠怎么学
一名花匠包装设计
养花技巧：老花匠教你三招，如何嫁接花木提高存活率！
幼儿园课件：花匠种花
卤蛋英雄花匠角色攻略
养花技巧：老花匠教你这三招，如何嫁接花木提高存活率！
小花匠
花匠解释
网址: 【NOIP2013提高组】花匠 https://m.huajiangbk.com/newsview530735.html
| 上一篇: Huahua's Tech Ro |
下一篇: 几月扦插最好 |
