AcWing登山

2021-05-18 05:30

阅读：531

标签：反向最大值 define div name 集合 clu acm under

这是2006北大举办的ACM的一道题。

题意为：给定景点海拔高度，队员们不去游览相同高度的景点，一开始往上爬，一但往下爬就不能再向上爬，求最多可以游览多少个景点。那么我们可以得到一个结论：以一个最高点为区分，前面的是最大上升子序列，后面的是最大下降子序列。然后我们就彻底把此传化为了LIS问题。我们开始思考：集合？以峰值为终点的最大子序列长度（一个1-n;一个n~1)。属性？最大值。划分依据与计算？以a[i]结尾的序列a[1],a[2],a[i-1],a[i]里找到a[j]。其次要注意这个反向的时候逆序来求，要再开一个集合。最后枚举峰值点即可。

代码

#include#define maxn 1010
using namespace std;
int dp1[maxn],dp2[maxn];
int n;
int a[maxn];
int main(){
    cin>>n;
    for(int i=1;i){
        cin>>a[i];
    }
    for(int i=1;i){
        dp1[i]=1;
        for(int j=1;j){
            if(a[i]>a[j]){
                dp1[i]=max(dp1[i],dp1[j]+1);
            }
        }
    }
    for(int i=n;i>=1;i--){
        dp2[i]=1;
        for(int j=n;j>i;j--){
            if(a[i]>a[j]){
                dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i){
        res=max(res,dp1[i]+dp2[i]-1);
    }
    cout;
    return 0;
}

AcWing登山

标签：反向最大值 define div name 集合 clu acm under

原文地址：https://www.cnblogs.com/china-mjr/p/11750025.html

上一篇：C#刷遍Leetcode面试题系列连载（5）：No.593 - 有效的正方形

下一篇：Macbook Pro 装Windows CPU 发热量过大的解决办法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing登山
文章链接：http://soscw.com/index.php/essay/87057.html

亲，登录后才可以留言！

AcWing登山

评论

热门文章

推荐文章

最新文章

置顶文章