历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1014. 登山问题中为什么不可以将【倒着遍历上升】替换为【正着遍历下降】？原题链接简单

作者：

YMYS , 2024-12-18 21:30:49 , 所有人可见 , 阅读 10

1、题目

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

2≤N≤1000

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

2、问题

我下面的代码有一块注释掉的双层for循环，该双层循环是【正着遍历下降】。
正常来说：【倒着遍历上升】与【正着遍历下降】不应该是一样的效果吗？为什么我把第27行的for循环（注释有提示哪个for循环是第27行）替换成我注释掉的那一个双层for循环后，代码就不可以AC了。

3、代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
int w[N],f[N],g[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    //正着走上升时
    for(int i=1;i<=n;i++){
        f[i] = 1;
        for(int j=1;j<i;j++){//1~i-1
            if(w[i]>w[j]){
                f[i] = max(f[i], f[j]+1);
            }
        }
    }

    //倒着走上升【也就是说：正着走下降】
    for(int i=n;i>=1;i--){//第27行
        g[i] = 1;
        for(int j=n;j>i;j--){//1~i-1
            if(w[i]>w[j]){
                g[i] = max(g[i], g[j]+1);
            }
        }
    }

    //以下这个循环替换成上面第27行那个循环后，就不能AC了
    //正着走下降
    //求每个点w[i]，正着走下降时的max_g[i]
    // for(int i=1;i<=n;i++){
    //     g[i] = 1;
    //     for(int j=1;j<i;j++){//1~i-1
    //         if(w[i]<w[j]){
    //             g[i] = max(g[i], g[j]+1);
    //         }
    //     }
    // }

    //为什么要减一呢，因为山峰那个点对于两条线【f[]、g[]】是重合的
    int res = 1;
    for(int i=1;i<=n;i++){
        res = max(res, f[i]+g[i]-1);
    }

    cout<<res<<endl;

    return 0;
}