每日算法--最长上升子序列--LIS

怪盗基德的滑翔翼

https://www.acwing.com/problem/content/description/1019/

题面：

解题思路：求出索格序列的最长上升子序列以及最长下降子序列，输出最大值即可

#include<iostream>
#include<string.h>
using namespace std;
int main(){
	int K,N;
	cin>>K;
	while(K--){
		cin>>N;/*楼的栋数*/
		int h[150];
		int dp[150]={0};
		for(int i=1;i<=N;i++){
			cin>>h[i];
		}/*输入数据完毕，下面开始求两个方向*/
		int max_len=-1;
		for(int i=1;i<=N;i++){
			dp[i]=1;
			for(int j=1;j<i;j++){
				if(h[j]<h[i]){
					dp[i]=max(dp[i],dp[j]+1);
					max_len=max(max_len,dp[i]);
				}
			}
		}
		memset(dp,0,sizeof(dp));
		int min_len=-1;
		for(int i=1;i<=N;i++){
			dp[i]=1;
			for(int j=1;j<i;j++){
				if(h[j]>h[i]){
					dp[i]=max(dp[i],dp[j]+1);
					min_len=max(min_len,dp[i]);
				}
			}
		}
		cout<<max(max_len,min_len)<<endl;
	}
	return 0;
}

登山

https://vjudge.net/problem/OpenJ_Bailian-2995

题面：

解题思路：本题也是LIS算法的简单应用，但有点小坑。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
//==================================
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int EPS=1e-6;
ll binarymod(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)
        res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
//利用二进制来算a的b次方的模板
//===================================
//=========================
int main(){
    ll N;
    cin>>N;
    int h[1010]={0};
    int dp[1010]={0};
    int dd[1010]={0};
    for(int i=1;i<=N;i++){
        cin>>h[i];
    }/*数据输入完毕，下面凯斯处理数据*/
    int max_len=-1;
    for(int i=1;i<=N;i++){/*计算上半部分结果*/
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(h[j]<h[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int h1[1010]={0},t=1;
    for(int i=N;i>=1;i--){
        h1[t++]=h[i];
    }
    for(int i=1;i<=N;i++){
        dd[i]=1;
        for(int j=1;j<i;j++){
            if(h1[j]<h1[i]){
                dd[i]=max(dd[i],dd[j]+1);
            }
        }
    }
    int dh[1010]={0};
    t=1;
    for(int i=N;i>=1;i--){
        dh[t++]=dd[i];
    }
    int max_sum=-1;
    for(int i=1;i<=N;i++){
        if(max_len<(dh[i]+dp[i])){
            max_len=dh[i]+dp[i];
        }
    }
    cout<<max_len-1<<endl;
    return 0;
}