AcWing登山

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

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

代码

#include<bits/stdc++.h>

#define maxn 1010

using namespace std;

int dp1[maxn],dp2[maxn];

int n;

int a[maxn];

int main(){

    cin>>n;

    for(int i=;i<=n;i++){

        cin>>a[i];

    }

    for(int i=;i<=n;i++){

        dp1[i]=;

        for(int j=;j<i;j++){

            if(a[i]>a[j]){

                dp1[i]=max(dp1[i],dp1[j]+);

            }

        }

    }

    for(int i=n;i>=;i--){

        dp2[i]=;

        for(int j=n;j>i;j--){

            if(a[i]>a[j]){

                dp2[i]=max(dp2[i],dp2[j]+);

            }

        }

    }

    int res=;

    for(int i=;i<=n;i++){

        res=max(res,dp1[i]+dp2[i]-);

    }

    cout<<n;

    return ;

}

巴特西

AcWing登山

最新文章

热门文章