鱼C论坛

 找回密码
 立即注册
查看: 1127|回复: 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

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

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

  6. int max(int a, int b)
  7. {
  8.     return a > b ? a : b;
  9. }

  10. int main()
  11. {
  12.     //freopen("data.txt", "r", stdin);
  13.     int n;
  14.     while (scanf("%d", &n) != EOF)
  15.     {
  16.         for (int i = 0; i < n; i++)
  17.         {
  18.             scanf("%d", &arr[i]);
  19.         }
  20.         int maxVal = 0;
  21.         for (int i = 0; i < n; i++)
  22.         {
  23.             dp[i] = arr[i];
  24.             for (int j = 0; j < i; j++)
  25.             {
  26.                 if (arr[i] > arr[j])
  27.                 { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
  28.                     dp[i] = max(dp[i], dp[j] + arr[i]);
  29.                     if (dp[i] > maxVal)
  30.                     {
  31.                         maxVal = dp[i];
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.         printf("%d\n", maxVal);
  37.     }
  38.     return 0;
  39. }
复制代码


  1.     input:
  2.         7
  3.         1 7 3 5 9 4 8
  4.     iuput:
  5.         18
复制代码



这是执行完成后,两个数组中的内容
  1. 1: arr = {1, 7, 3, 5, 9, 4, 8, 0 <repeats 1003 times>}
  2. 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

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

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

  6. int max(int a, int b)
  7. {
  8.     return a > b ? a : b;
  9. }

  10. int main()
  11. {
  12.     //freopen("data.txt", "r", stdin);
  13.     int n;
  14.     while (scanf("%d", &n) != EOF)
  15.     {
  16.         for (int i = 0; i < n; i++)
  17.         {
  18.             scanf("%d", &arr[i]);
  19.         }
  20.         int maxVal = 0;
  21.         for (int i = 0; i < n; i++)
  22.         {
  23.             dp[i] = arr[i];
  24.             for (int j = 0; j < i; j++)
  25.             {
  26.                 if (arr[i] > arr[j])
  27.                 { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
  28.                     dp[i] = max(dp[i], dp[j] + arr[i]);
  29.                     if (dp[i] > maxVal)
  30.                     {
  31.                         maxVal = dp[i];
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.         printf("%d\n", maxVal);
  37.     }
  38.     return 0;
  39. }
复制代码


  1.     input:
  2.         7
  3.         1 7 3 5 9 4 8
  4.     iuput:
  5.         18
复制代码



这是执行完成后,两个数组中的内容
  1. 1: arr = {1, 7, 3, 5, 9, 4, 8, 0 <repeats 1003 times>}
  2. 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

  1. #include <iostream>
  2. #include <vector>

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

  9. bool change_flag(std::vector<bool> &flag) {
  10.     for(size_t i = 0; i < flag.size() - 1; ++i) {
  11.         if(flag[i] && !flag[i + 1]) {
  12.             flag[i] = false; flag[i + 1] = true;
  13.             size_t count = 0;
  14.             for(size_t j = 0; j < i; ++j) if(flag[j]) ++count;
  15.             for(size_t j = 0; j < i; ++j) flag[j] = false;
  16.             for(size_t j = 0; j < count; ++j) flag[j] = true;
  17.             return true;
  18.         }
  19.     }
  20.     return false;
  21. }

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

  30. void filter(std::vector<std::vector<int>> &data) {
  31.     for(size_t i = 0; i < data.size(); ++i) {
  32.         for(size_t j = 0; j < data[i].size() - 1; ++j) {
  33.             if(data[i][j] > data[i][j + 1]) {
  34.                 data.erase(data.begin() + i);
  35.                 --i; break;
  36.             }
  37.         }
  38.     }
  39. }

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

  48. size_t max(const std::vector<std::vector<int>> &data) {
  49.     size_t max_value = 0;
  50.     for(const auto &iter: data) {
  51.         size_t sum = 0;
  52.         for(const auto &e: iter) sum += e;
  53.         if(max_value < sum) max_value = sum;
  54.     }
  55.     return max_value;
  56. }

  57. int main() {
  58.     std::cout << "请输入: ";
  59.     size_t size;
  60.     std::cin >> size;
  61.     std::vector<int> data;
  62.     for(size_t i = 0; i < size; ++i) {
  63.         size_t e;
  64.         std::cin >> e;
  65.         data.push_back(e);
  66.     }
  67.     std::cout << max(get_subsequence(data)) << std::endl;
  68.     return 0;
  69. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> 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

GMT+8, 2023-2-9 11:47

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

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