三关求调站外题
  • 板块灌水区
  • 楼主NOIPwjy2011
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/10 13:45
  • 上次更新2024/11/10 13:46:02
查看原帖
三关求调站外题
1078995
NOIPwjy2011楼主2024/11/10 13:45

题目描述:

五一到了,ACM队组织大家去登山观光,队员们发现山上一个有N个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?

输入:

第一行:N(2N1000)N (2 ≤ N ≤ 1000) 景点数;

第二行:N个整数,每个景点的海拔。

输出:

最多能浏览的景点数。

入样:

8
186 186 150 200 160 130 197 220

出样:

4

蒟蒻代码:

#include<bits/stdc++.h>
using namespace std;
/*
①设置状态 
	dp[i]设置为以i结尾的最长下降子串 
②确定答案 
	max{dp[i]}
③确定状态转移方程 
	一种是继续下降:a[i]至少比a[j]低
		dp[i]=max{dp[j]+1}
		j>i,j是之前所有可能的答案
	另外一种是自立门户:dp[i]=1
		dp[i]=max{dp[j]+1,dp[i]}
④确定初始状态和边界情况 
	dp[i]=1 
*/
int dp[10000005];
int a[10000005];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	int maxx=1;
	bool flag_down=false;
	bool flag_up=false;
	for(int i=1;i<=n;i++){
		dp[i]=1;
		if(a[i]>a[i-1] && flag_up==0){
			flag_down=1;
			dp[i]=max(dp[i-1]+1,dp[i]);
		}
		if(a[i]<a[i-1] && flag_down==1){
			flag_up=1;
			dp[i]=max(dp[i-1]+1,dp[i]);
		}
		maxx=max(maxx,dp[i]);
		//cout<<dp[i]<<" "<<i<<endl;
	}
	cout<<maxx;
   	return 0;
}

求各位大佬改改蒟蒻的代码awa

2024/11/10 13:45
加载中...