40,TLE两个，求调（玄关

CASEY_lzpF @ 2024-08-06 22:21:42

#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <stack>
#define int long long
#define float double
using namespace std;
int n;
int a[5001];
int ans;
int mx=-1;
void dp(int i,int x){
    if(i == n){
        mx = max(mx,x);
        return ;
    }
    for(int j = i;j<=n;j++){ 
        if(a[i] < a[j]){
            dp(j,x+1);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    dp(1,1);
    cout<<mx;
    return 0;
}

by ___LuXun___ @ 2024-08-06 22:39:54

@CASEY_lzpF 你真刻苦

by ___LuXun___ @ 2024-08-06 22:40:51

@CASEY_lzpF 现在人们不爱调了，你去vx老师吧

by haimingbei @ 2024-08-06 22:47:36

@CASEY_lzpF AC,求关

现在人不爱调，只爱直接发代码

/*
B3637 最长上升子序列
*/
#include<bits/stdc++.h>
using namespace std;
int a[5005],dp[5005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    sort(dp+1,dp+n+1);
    cout<<dp[n];
    return 0;
}

by CASEY_lzpF @ 2024-08-06 22:52:42

@haimingbei 好像也是，我这估计是没记忆化

by nyk1315 @ 2024-08-07 17:12:34

//解 
#include<bits/stdc++.h>
using namespace std;
int n,x;
vector<int>nums;
int dp(){
    int n=nums.size();//获取vector容器中元素个数 
    if(n==0)//如果n的值为0,表示最长上升子序列为0 
        return 0;
    vector<int>a(n,1);//创造a容器大小为n初值为1 
    int ans=1;//至少有一个元素最长子序列为1
    for(int i=1;i<n;i++){//循环遍历nums数组  
        for(int j=0;j<i;j++)//循环遍历i之前的数据 
            if(nums[j]<nums[i])//如果i之前的数据小于i的位置的数据 
                a[i]=max(a[i],a[j]+1);//上升子序列的长度增加1 
    ans=max(ans,a[i]);//如果ans和a[i]比较上升子序列长度 
    }
    return ans;//返回ans 
}
int main(){
    freopen("std.in","r",stdin);
    //freopen("std.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        nums.push_back(x);
    } 
    cout<<dp();
    return 0;
}

这是我的代码可以参考一下求关

by wangzaixi @ 2024-08-19 15:52:51

AC

#include<iostream>
using namespace std;
int n,a[5001],dp[5001];
int Max(int ans[],int l){//数组最大值
    int m=0;
    for(int i=0;i<l;i++){
        m=max(m,ans[i]);
    }
    return m;
}
void LIS(){//LIS走起!
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[i],dp[j]+1);//状态转移方程:dp[i]=max(dp[i],dp[j]+1)
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    LIS();
    cout<<Max(dp,n)+1;
    return 0;
}

by wangzaixi @ 2024-08-19 15:53:45

@wangzaixi 注释较少，别打我

by wangzaixi @ 2024-08-19 15:55:56

@wangzaixi 思路 状态转移方程:

by CASEY_lzpF @ 2024-08-19 16:32:12

@wangzaixi 感谢，不过我已经AC了（是不是应该发个此贴结？）

by wangzaixi @ 2024-08-25 08:47:24

@CASEY_lzpF yes