论坛 › C\C++交流 › 最大上升子序列和（关于基本动态规划的一道问题）

bangbang-ande 发表于 2021-2-25 18:57:39

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

本帖最后由 bangbang-ande 于 2021-3-5 23:37 编辑

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



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

@不二如是   审核下

人造人 发表于 2021-2-25 18:57:40

那就看标准答案吧
https://www.nowcoder.com/questionTerminal/dcb97b18715141599b64dbdb8cdea3bd

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

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

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);
      }
      int maxVal = 0;
      for (int i = 0; i < n; i++)
      {
            dp = arr;
            for (int j = 0; j < i; j++)
            {
                if (arr > arr)
                { // 满足递增的子序列, 记录下 dp 是子序列的和
                  dp = max(dp, dp + arr);
                  if (dp > maxVal)
                  {
                        maxVal = dp;
                  }
                }
            }
      }
      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 发表于 2021-2-28 11:16:59

帖子还没人答，顶一顶{:7_146:}

人造人 发表于 2021-2-28 11:42:12

c or c++ ?

bangbang-ande 发表于 2021-2-28 12:45:04

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

使用c或c++都行

人造人 发表于 2021-2-28 13:25:17

我研究研究

人造人 发表于 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) result.push_back(data);
    return result;
}

bool change_flag(std::vector<bool> &flag) {
    for(size_t i = 0; i < flag.size() - 1; ++i) {
      if(flag && !flag) {
            flag = false; flag = true;
            size_t count = 0;
            for(size_t j = 0; j < i; ++j) if(flag) ++count;
            for(size_t j = 0; j < i; ++j) flag = false;
            for(size_t j = 0; j < count; ++j) flag = 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 = 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.size() - 1; ++j) {
            if(data > data) {
                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 22:53:14

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

好像会超过时间限制

人造人 发表于 2021-3-1 09:21:56

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

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

bangbang-ande 发表于 2021-3-1 18:04:40

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

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

人造人 发表于 2021-3-1 19:06:29

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

嗯

查看完整版本: 最大上升子序列和（关于基本动态规划的一道问题）