[已解决]最大上升子序列和（关于基本动态规划的一道问题）

bangbang-ande

本题链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1285

本题图片

这道题有点难度，用了dp，但做不出来，大神们提供下思路
（代码可以不写）

@不二如是   审核下

最佳答案

月排行榜 / 总排行榜

人造人

2021-2-25 18:57:40

那就看标准答案吧
https://www.nowcoder.com/questio ... 1599b64dbdb8cdea3bd

#include <stdio.h>
#include <stdint.h>

#define N 1010
int arr[N];
int dp[N]; //  最长递增子序列

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }
        int maxVal = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j])
                { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
                    dp[i] = max(dp[i], dp[j] + arr[i]);
                    if (dp[i] > maxVal)
                    {
                        maxVal = dp[i];
                    }
                }
            }
        }
        printf("%d\n", maxVal);
    }
    return 0;
}

    input:
        7
        1 7 3 5 9 4 8
    iuput:
        18

这是执行完成后，两个数组中的内容

1: arr = {1, 7, 3, 5, 9, 4, 8, 0 <repeats 1003 times>}
2: dp = {1, 8, 4, 9, 18, 8, 17, 0 <repeats 1003 times>}

如果看不懂代码，你可以调试一下，看看每一步后，dp数组的变化

跳转到最佳答案楼层

人造人

那就看标准答案吧
https://www.nowcoder.com/questio ... 1599b64dbdb8cdea3bd

#include <stdio.h>
#include <stdint.h>

#define N 1010
int arr[N];
int dp[N]; //  最长递增子序列

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }
        int maxVal = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j])
                { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
                    dp[i] = max(dp[i], dp[j] + arr[i]);
                    if (dp[i] > maxVal)
                    {
                        maxVal = dp[i];
                    }
                }
            }
        }
        printf("%d\n", maxVal);
    }
    return 0;
}

    input:
        7
        1 7 3 5 9 4 8
    iuput:
        18

这是执行完成后，两个数组中的内容

1: arr = {1, 7, 3, 5, 9, 4, 8, 0 <repeats 1003 times>}
2: dp = {1, 8, 4, 9, 18, 8, 17, 0 <repeats 1003 times>}

如果看不懂代码，你可以调试一下，看看每一步后，dp数组的变化

bangbang-ande

帖子还没人答，顶一顶

人造人

c or c++ ?

bangbang-ande

人造人 发表于 2021-2-28 11:42
c or c++ ?

使用c或c++都行

人造人

我研究研究

人造人

思路就是穷举，先得到所有的组合，然后过滤掉不合格的，然后计算最大值
参考 https://blog.csdn.net/ajian005/article/details/22265507

#include <iostream>
#include <vector>

const std::vector<int> get_element(const std::vector<int> &data, const std::vector<bool> &flag) {
    std::vector<int> result;
    if(data.size() != flag.size()) throw "data.size() != flag.size()";
    for(size_t i = 0; i < flag.size(); ++i) if(flag[i]) result.push_back(data[i]);
    return result;
}

bool change_flag(std::vector<bool> &flag) {
    for(size_t i = 0; i < flag.size() - 1; ++i) {
        if(flag[i] && !flag[i + 1]) {
            flag[i] = false; flag[i + 1] = true;
            size_t count = 0;
            for(size_t j = 0; j < i; ++j) if(flag[j]) ++count;
            for(size_t j = 0; j < i; ++j) flag[j] = false;
            for(size_t j = 0; j < count; ++j) flag[j] = true;
            return true;
        }
    }
    return false;
}

const std::vector<std::vector<int>> combine(const std::vector<int> &data, size_t n) {
    std::vector<std::vector<int>> result;
    std::vector<bool> flag(data.size(), false);
    for(size_t i = 0; i < n; ++i) flag[i] = true;
    result.push_back(get_element(data, flag));
    while(change_flag(flag)) result.push_back(get_element(data, flag));
    return result;
}

void filter(std::vector<std::vector<int>> &data) {
    for(size_t i = 0; i < data.size(); ++i) {
        for(size_t j = 0; j < data[i].size() - 1; ++j) {
            if(data[i][j] > data[i][j + 1]) {
                data.erase(data.begin() + i);
                --i; break;
            }
        }
    }
}

const std::vector<std::vector<int>> get_subsequence(const std::vector<int> &data) {
    std::vector<std::vector<int>> result;
    for(size_t i = 0; i <data.size(); ++i) {
        std::vector<std::vector<int>> v = combine(data, i + 1);
        filter(v); for(const auto &j: v) result.push_back(j);
    }
    return result;
}

size_t max(const std::vector<std::vector<int>> &data) {
    size_t max_value = 0;
    for(const auto &iter: data) {
        size_t sum = 0;
        for(const auto &e: iter) sum += e;
        if(max_value < sum) max_value = sum;
    }
    return max_value;
}

int main() {
    std::cout << "请输入: ";
    size_t size;
    std::cin >> size;
    std::vector<int> data;
    for(size_t i = 0; i < size; ++i) {
        size_t e;
        std::cin >> e;
        data.push_back(e);
    }
    std::cout << max(get_subsequence(data)) << std::endl;
    return 0;
}

bangbang-ande

人造人 发表于 2021-2-28 17:33
思路就是穷举，先得到所有的组合，然后过滤掉不合格的，然后计算最大值
参考 https://blog.csdn.net/ajian ...

好像会超过时间限制

人造人

bangbang-ande 发表于 2021-2-28 22:53
好像会超过时间限制

你那边显示超时？我这边说我编译错误

bangbang-ande

人造人 发表于 2021-3-1 09:21
你那边显示超时？我这边说我编译错误

因为这题用穷举会超时（这是我相信的）

人造人

bangbang-ande 发表于 2021-3-1 18:04
因为这题用穷举会超时（这是我相信的）

嗯