40pts,WA 4,5,6,求助，揪出必关~

liuzhouyang @ 2024-08-21 16:58:10

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[5005],dp[5005];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    cout<<dp[n];
}

by lzh_juruo @ 2024-08-21 17:04:24

@liuzhouyang

答案应为dp[1]到dp[n]取最大值

by I_AM_joker @ 2024-08-21 17:04:46

@liuzhouyang 要再开一个循环遍历dp数组 代码如下：

int ans=-11451;
for (int i = 1;i<=n;i++) {
    ans=max(ans,dp[i]);
}
cout<<ans<<endl;

by 违规用户名K&xs3Z^ @ 2024-08-21 17:15:09

@liuzhouyang 每次循环取最大值 不能保证最后一个一定是最大值

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[5005],dp[5005],maxn=-1;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        maxn=max(maxn,dp[i]);
    }
    cout<<maxn;
}

by 违规用户名K&xs3Z^ @ 2024-08-21 17:16:07

@liuzhouyang 方法二 函数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int s[N],top;
long long a[N],w[N],ans,n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        if(s[top]>=a[i]){
            s[lower_bound(s+1,s+1+top,a[i])-s]=a[i];
        }else{

            s[++top]=a[i];
        }
    }
    cout<<top<<endl;
    return 0;
}

by liuzhouyang @ 2024-08-21 17:42:08

谢谢大家。此帖结！

by hanchengjingpeter @ 2024-08-22 14:02:09

后排兜售小曼巴

by zhaoyonghao @ 2024-08-27 19:37:26

@liuzhouyang 建议你写一下dp数字存的是什么东西这样不容易出错

int a[1005], f[1005];//以第i个数字结尾的最长上升子序列 

你不能确保最长上升子序列一定是最后一个数字结尾，应该从1~n里找最大值

int ans = 0;
for (int i = 1; i <= n; i++)
    ans = max(f[i], maxn);
cout << ans << "\n";