WA(40)求助

IOI_AK_TLR @ 2023-07-27 13:42:24

#include <bits/stdc++.h>
using namespace std;
const int N(5005);
int a[N]={INT_MIN},dp[N]={0,1},n,ans=INT_MIN;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)
            continue;
        int j=i-1;
        while(a[j]>=a[i])
            j--;
        dp[i]=dp[j]+1;
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

by zhlzt @ 2023-07-27 13:46:44

@IOI_AK_TLR 为什么以 i 结尾的最长上升子序列的倒数第二个数一定是比他小在他前面的的最后面的数？ 比如这一组数据：[2,3,1,4]，显然，以 4 结尾的最长上升子序列的倒数第二个数是 3 而不是 1。

by IOI_AK_TLR @ 2023-07-27 13:52:35

@Special_Tony OK明白了，非常感谢！

by IOI_AK_TLR @ 2023-07-27 14:01:39

@Special_Tony 我改了一下，原先的错误是解决了，但是还是40分怎么办：

#include <bits/stdc++.h>
using namespace std;
const int N(5005);
int a[N]={INT_MIN},dp[N]={0,1},n,ans=INT_MIN;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)
            continue;
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
                dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

by zhlzt @ 2023-07-27 14:11:06

@IOI_AK_TLR 您有没有考虑过，以一个数结尾的最长上升子序列就是他自己呢？所以得给所有 dp_i 赋初始值 1，代码如下：

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

by IOI_AK_TLR @ 2023-07-27 14:17:15

@Special_Tony 原来如此！感谢大佬