动态规划求助，40pts，WA后三个点

silent_ST @ 2023-08-22 12:07:34

#include <iostream>
using namespace std;
long long f[5005], a[5005];
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(a[i] > a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    cout << f[n];
    return 0;
}

by silent_ST @ 2023-08-22 12:08:56

不在线，可能不会按时回复，望谅解

by RKSSSKR @ 2023-08-22 12:16:23

维护一个数组 dp，其中 dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。这样，dp 数组是一个递增的数组。初始化时，dp 数组全部设置为 INF，表示无穷大。 然后遍历原序列，对于每个元素，在 dp 数组中找到第一个大于等于它的数，将其替换为该元素。如果该元素比 dp 数组中的所有元素都大，那么将其追加到 dp 数组的末尾。 最后，dp 数组的长度即为所求的最长上升子序列的长度。 通过这种方式，可以将算法的时间复杂度从 O(n^2) 优化到 O(nlogn)。

//ac代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9+7;
int main() {
    int n;
    cin >> n;

    vector<int> dp(n+1, INF);
    dp[0] = -INF;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        int pos = upper_bound(dp.begin(), dp.end(), num) - dp.begin();
        if (num > dp[pos-1]) {
            dp[pos] = num;
        }
    }

    int ans = 0;
    for (int i = n; i >= 0; i--) {
        if (dp[i] != INF) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

by RKSSSKR @ 2023-08-22 12:21:01

找到dp数组中第一个大于num的位置pos。 如果当前数num大于dp数组中pos-1位置的数，则更新dp数组中pos位置的值为num。 循环结束后，dp数组中有效数的个数即为最长递增子序列的长度。 在倒序遍历dp数组，找到第一个不为INF的数，即为最长递增子序列的长度。

by xvl_ @ 2023-08-22 12:25:36

@silent_ST

需要对所有状态求个最大值

#include <iostream>
using namespace std;
long long f[5005], a[5005];
long long n, ans;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        f[i] = 1;
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(a[i] > a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout << ans;
    return 0;
}

by _GJM_ @ 2023-08-22 12:30:45

@silent_ST 最后加上这个

    for(int i = 1; i <= n; i++){
        Max = max(Max, dp[i]);
    }

by _GJM_ @ 2023-08-22 12:31:54

#include <bits/stdc++.h>
using namespace std;
int dp[5005], a[5005], n, Max;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        dp[i] = 1;
        cin >> a[i];
    }
    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);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        Max = max(Max, dp[i]);
    }
    cout << Max;
    return 0;
}

by silent_ST @ 2023-08-22 13:23:51

thx，此帖结

by silent_ST @ 2023-08-22 13:25:36

感谢 @RKYSSS @xvl_ @GJM 的帮助！

by pandaishun61 @ 2023-09-25 21:22:28

@silent_ST 最后一个不一定是最大的 用一个ans来存最大的 最后输出ans