讨论

全局板块

原题链接:https://www.luogu.com.cn/problem/P1970?contestId=55565
~~标签写着dp读作贪心~~
这题刚开始没想到任何思路然后悄咪咪的点开标签，一看dp，便觉得~~自己行了~~
结果还是一脸懵 ~~还是题解好~~

先对给出的两个需满足的条件进行分析

A:满足所有的 g_2i>g_2i-1,g_2i>g_2i+1
B:满足所有的 g_2i<g+2i-1,g_2i<g_2i+1

稍加分析可以看出条件有着这样的规律

A:谷底[奇] 谷峰[偶] 谷底[奇]
B:谷峰[奇] 谷底[偶] 谷峰[奇]
也就是说选出的花要成波浪状，这就巧妙的将A和B条件合并了

如果要最后剩下的花最多，那么第一朵花必选，只有这样才能使 备选花 的数量达到最大
如果从第二个开始的话， 备选花 就比从第一个少一个
这时只要找到第二朵花就将它与第一朵相比，看第二朵满足的是谷 or 峰，如果与第一朵相等就舍弃

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N];
int f[N][2];//i--第几朵花  j--谷底r谷峰[0--谷 1--峰]
inline int read(){
	register int ans=0,t=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') t=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ans=ans*10+(ch-'0');
		ch=getchar();
	}
	return ans*t;
}
int main(){
	int n;
	n=read();
	for(int i=1;i<=n;i++) h[i]=read();
	f[1][0]=f[1][1]=1;//0--谷 1--峰 
	for(int i=2;i<=n;i++){
		if(h[i]>h[i-1]) f[i][1]=f[i-1][0]+1;//从谷底转移过来 
		else f[i][1]=f[i-1][1];//不转移 
		if(h[i]<h[i-1]) f[i][0]=f[i-1][1]+1;//从谷峰转移过来 
		else f[i][0]=f[i-1][0];//不转移 
	}
	cout<<max(f[n][0],f[n][1]);
	return 0;
}

小声:个人认为偶尔打个快读其实是能提高~~暴力ak~~的概率的
~~加工零件的那一道暴力方法打个快读能多5分~~
~~指不定这5分就干倒某猪拱白菜的学校了~~

2020we

2022-03-26 21:09:34

%%%%%%%

Star

2022-03-26 20:44:12

不要脸地补充一个贪心做法

思路主要是一升一降，选择上升的一段中最大的那个点(即一段上升序列的最后一个点)，这样可以给之后留出最多的余地，同样选择下降的一段中最小的那个点(即一段下降序列的最后一个点)，每次转弯(上升 -> 下降 || 下降 -> 上升)时统计次数。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int h[N];

int main() {
    int n, i;
    int res = 0;
    scanf("%d", &n);
    for(i = 1; i <= n; ++i) scanf("%d", &h[i]);
    i = 1;
    //因为本人很菜，特判相等好像会有一些bug
	n = unique(h + 1, h + 1 + n) - h - 1;
    while(i <= n) {
        if(h[i] < h[i - 1]) { //下降
            int t = i - 1;
            while(h[i] < h[i - 1]) ++i;
            res += 1;
        }
        else { //上升
            int t = i - 1;
            while(h[i] > h[i - 1]) ++i;
            res += 1;
        }
    }
    //特判第一个点，如果上升，因为第0个点是0，判断上升时会少统计第一个点
    if(h[2] > h[1]) ++res;
    printf("%d", res);
    return 0;
}

Laffey

2022-03-26 20:29:50

花匠

共 3 条回复

%%%%%%%

不要脸地补充一个贪心做法

%%%%%%%