三关求助站外DP题

【题目描述】

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

【输入】

第一行：

N (2 ≤ N ≤ 1000)

景点数;

第二行：N个整数，每个景点的海拔。

【输出】

最多能浏览的景点数。

【输入样例】

CPP

8
186 186 150 200 160 130 197 220

【输出样例】

CPP

蒟蒻代码：

#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;
}

求助各位大佬改改我的代码

三关求助站外DP题

讨论操作

回复

相关推荐

三关求助站外DP题