鱼C论坛

 找回密码
 立即注册
查看: 2573|回复: 10

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

[复制链接]
发表于 2021-2-25 18:57:39 | 显示全部楼层 |阅读模式
8鱼币
本帖最后由 bangbang-ande 于 2021-3-5 23:37 编辑

本题链接: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/questionTerminal/dcb97b18715141599b64dbdb8cdea3bd 这是执行完成后,两个数组中的内容 如果看不懂代码,你可以调试一下,看看每一步后,dp数组的变化
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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数组的变化
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-2-28 11:16:59 | 显示全部楼层
帖子还没人答,顶一顶
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-2-28 11:42:12 | 显示全部楼层
c or c++ ?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-2-28 12:45:04 | 显示全部楼层

使用c或c++都行
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-2-28 13:25:17 | 显示全部楼层
我研究研究
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-2-28 17:33:33 | 显示全部楼层
思路就是穷举,先得到所有的组合,然后过滤掉不合格的,然后计算最大值
参考 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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-2-28 22:53:14 From FishC Mobile | 显示全部楼层
人造人 发表于 2021-2-28 17:33
思路就是穷举,先得到所有的组合,然后过滤掉不合格的,然后计算最大值
参考 https://blog.csdn.net/ajian ...

好像会超过时间限制
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-3-1 09:21:56 | 显示全部楼层
bangbang-ande 发表于 2021-2-28 22:53
好像会超过时间限制

你那边显示超时?我这边说我编译错误
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-3-1 18:04:40 | 显示全部楼层
人造人 发表于 2021-3-1 09:21
你那边显示超时?我这边说我编译错误

因为这题用穷举会超时(这是我相信的)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-3-1 19:06:29 | 显示全部楼层
bangbang-ande 发表于 2021-3-1 18:04
因为这题用穷举会超时(这是我相信的)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-7-18 04:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表