关于NOIP2013（P1970）花匠
先看看题
题目描述
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数 h_1,h_2,...,h_nh1,h2,...,hn 。设当一部分花被移走后，剩下的花的高度依次为 g_1,g_2,...,g_mg1,g2,...,gm ，则栋栋希望下面两个条件中至少有一个满足：
条件 AA ：对于所有 g_{2i}>g_{2i-1},g_{2i}>g_{2i+1}g2i>g2i−1,g2i>g2i+1
条件 BB ：对于所有 g_{2i}<g_{2i-1},g_{2i}<g_{2i+1}g2i<g2i−1,g2i<g2i+1
注意上面两个条件在 m=1m=1 时同时满足，当 m > 1m>1 时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
输入输出格式
输入格式：
第一行包含一个整数 nn ，表示开始时花的株数。
第二行包含 nn 个整数，依次为 h_1,h_2,...,h_nh1,h2,...,hn ,表示每株花的高度。
输出格式：
一个整数 mm ，表示最多能留在原地的花的株数。
输入输出样例
输入样例#1： 复制
5
5 3 2 1 2
输出样例#1： 复制
3
说明
【输入输出样例说明】
有多种方法可以正好保留 33 株花，例如，留下第 11 、 44 、 55 株，高度分别为 55 、 11 、 22 ，满足条件 B。
【数据范围】
对于 20%20% 的数据， n ≤ 10n≤10 ；
对于 30%30% 的数据， n ≤ 25n≤25 ；
对于 70%70% 的数据， n ≤ 1000,0 ≤ h_i≤ 1000n≤1000,0≤hi≤1000 ；
对于 100%100% 的数据， 1 ≤ n ≤ 100,000,0 ≤ h_i≤ 1,000,0001≤n≤100,000,0≤hi≤1,000,000 ，所有的 h_ihi 随机生成，所有随机数服从某区间内的均匀分布。
------------------------------------------------------------------------------------------
第一种解法
--------------巧妙的DP大法（Woc）此题解法巧妙
用到了DP思想
通过观察题面可以发现递推关系
于是可以用两个数组分别记录到i下降和到i上升
容易得出递推公式
if(a[i]>a[i-1])f[i][0]=f[i-1][1]+1;
else f[i][0]=f[i-1][0];
if(a[i]<a[i-1])f[i][1]=f[i-1][0]+1;
else f[i][1]=f[i-1][1];
代码君奉上
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int a[N],f[N][2]={0};
int n,tmp=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
f[1][0]=f[1][1]=1;
for(int i=2;i<=n;i++){
if(a[i]>a[i-1])f[i][0]=f[i-1][1]+1;
else f[i][0]=f[i-1][0];
if(a[i]<a[i-1])f[i][1]=f[i-1][0]+1;
else f[i][1]=f[i-1][1];
}
cout<<max(f[n][0],f[n][1]);
return 0;
}
---------------------------------------------------------------------------------------------
第二种解法
------更巧妙的贪心（Orz）我们可以对这个题进行谈心，我们考虑一下这个题的对于采取数据的本质。
题目是这么描述的：
条件 AA ：对于所有 g_{2i}>g_{2i-1},g_{2i}>g_{2i+1}g2i>g2i−1,g2i>g2i+1
条件 BB ：对于所有 g_{2i}<g_{2i-1},g_{2i}<g_{2i+1}g2i<g2i−1,g2i<g2i+1
那么也就是说存在这么一个g_(2i)点满足大于两边的数字或者小于两边的数字。
假设有N朵花
大致根据我们学过的函数思想，我们可以知道，存在mm个g(2i)点在波峰或波谷上。
因为在波峰到波谷或者从波谷到波峰上的点单调，所以不满足这个性质，我们决定舍去这些点。
那么对于什么样的点留下呢，我们可以取那些波峰和波谷。
我们可以打标记，用flag表示。再定义一个计数的ans。
我们首先肯定要取1点，并且1点肯定是一个波峰或波谷（这个很重要）
所以我们先判断一下hi[1]和hi[2]的关系（hi [ ]表示高度）
如果hi[1]<hi[2] 说明1是波谷，那么我们标记flag=-1 如果hi[1]>hi[2] 说明1是波峰，那么我们标记flag=1
所以我们只需要判断是否hi[i]*flag>h[i+1]*flag 如果是的话 ，那么ans++; 否则说明状态改变了，那么就让标记flag*=-1
通过一个for循环，我们就求出了ans的值
所以我们只需输出：（N-ans）
基本思想分析完了，我们来看看图示
好，下面我们来看代码（时间复杂度O(N)）
#include <iostream>
using namespace std;
int main()
{
int N;
int hi[1000001]={0};
int ans=0;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>hi[i];
}
int flag;
if(hi[1]>hi[2]) flag=1;
else flag=-1;
for(int i=2;i<=N-1;i++)
{
if(hi[i]*flag>=hi[i+1]*flag) ans++;
else flag*=-1; }
cout<<N-ans;
}
相关知识
小花匠
花匠解释
花匠品牌设计
星球重启小花匠怎么样
花匠：最幸福的职业 - 职业生涯规划
花匠鲜花加盟
花匠先生鲜花加盟 花匠先生鲜花加盟费 加盟怎么样
花匠与花作文
幼儿园课件：花匠种花
一名花匠包装设计
网址: 关于NOIP2013（P1970）花匠 https://m.huajiangbk.com/newsview529460.html
| 上一篇: 花匠（动态规划） |
下一篇: NOIP2013 花匠 题解（方 |
