求调

wisdom2010 @ 2024-07-27 08:24:16

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5 + 10;
int a[maxn];
int dp[maxn];
int longest;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 1;
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j < i; j++)
            if(a[j] <= a[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        longest = max(dp[i], longest);
    }
    //printf("%d", dp[n]);
    printf("%d", longest);
    return 0;
}

by DreamInk @ 2024-07-27 08:26:33

@wisdom2010

将

a[j] <= a[i]

改为

a[j] < a[i]

by DreamInk @ 2024-07-27 08:27:54

@wisdom2010 题目说了喔：这些数字是逐渐增大的

by wisdom2010 @ 2024-07-27 08:29:28

@DreamInk 哦哦哦，谢谢指点，已经AC了，thankyou

by wisdom2010 @ 2024-07-27 08:40:14

@DreamInk 但是为什么写成这样就不行？

by wisdom2010 @ 2024-07-27 08:40:31

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5 + 10;
int a[maxn];
int dp[maxn];
int longest;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 1;
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j < i; j++)
            if(a[j] < a[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        longest = max(dp[i], longest);
    }
    printf("%d", dp[n]);
    //printf("%d", longest);
    return 0;
}

@DreamInk

by wisdom2010 @ 2024-07-27 08:41:37

@DreamInk dp[i]表示前i个元素的最长上升子序列的长度

by DreamInk @ 2024-07-27 10:57:19

@wisdom2010

因为dp[n]不一定是最终答案

by DreamInk @ 2024-07-27 11:02:22

@wisdom2010

你可以去看看题解

它里面的图

dp[n]显然不是最终答案

by DreamInk @ 2024-07-27 11:03:45

@DreamInk 抱歉啊，你还是去看题解的图吧，n如果=4，dp[n]就不是最终答案

by wisdom2010 @ 2024-07-27 11:06:37

@DreamInk 哦，那 dp[i]就表示以 a[i] 为结尾的最长不下降子序列的长度呗？