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

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

1. #include <stdio.h>
   
2. #include <stdint.h>
   
3. 
   
4. #define N 1010
   
5. int arr[N];
   
6. int dp[N]; //  最长递增子序列
   
7. 
   
8. int max(int a, int b)
   
9. {
   
10.     return a > b ? a : b;
    
11. }
    
12. 
    
13. int main()
    
14. {
    
15.     //freopen("data.txt", "r", stdin);
    
16.     int n;
    
17.     while (scanf("%d", &n) != EOF)
    
18.     {
    
19.         for (int i = 0; i < n; i++)
    
20.         {
    
21.             scanf("%d", &arr[i]);
    
22.         }
    
23.         int maxVal = 0;
    
24.         for (int i = 0; i < n; i++)
    
25.         {
    
26.             dp[i] = arr[i];
    
27.             for (int j = 0; j < i; j++)
    
28.             {
    
29.                 if (arr[i] > arr[j])
    
30.                 { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
    
31.                     dp[i] = max(dp[i], dp[j] + arr[i]);
    
32.                     if (dp[i] > maxVal)
    
33.                     {
    
34.                         maxVal = dp[i];
    
35.                     }
    
36.                 }
    
37.             }
    
38.         }
    
39.         printf("%d\n", maxVal);
    
40.     }
    
41.     return 0;
    
42. }
    

复制代码

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/questio ... 1599b64dbdb8cdea3bd

1. #include <stdio.h>
   
2. #include <stdint.h>
   
3. 
   
4. #define N 1010
   
5. int arr[N];
   
6. int dp[N]; //  最长递增子序列
   
7. 
   
8. int max(int a, int b)
   
9. {
   
10.     return a > b ? a : b;
    
11. }
    
12. 
    
13. int main()
    
14. {
    
15.     //freopen("data.txt", "r", stdin);
    
16.     int n;
    
17.     while (scanf("%d", &n) != EOF)
    
18.     {
    
19.         for (int i = 0; i < n; i++)
    
20.         {
    
21.             scanf("%d", &arr[i]);
    
22.         }
    
23.         int maxVal = 0;
    
24.         for (int i = 0; i < n; i++)
    
25.         {
    
26.             dp[i] = arr[i];
    
27.             for (int j = 0; j < i; j++)
    
28.             {
    
29.                 if (arr[i] > arr[j])
    
30.                 { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
    
31.                     dp[i] = max(dp[i], dp[j] + arr[i]);
    
32.                     if (dp[i] > maxVal)
    
33.                     {
    
34.                         maxVal = dp[i];
    
35.                     }
    
36.                 }
    
37.             }
    
38.         }
    
39.         printf("%d\n", maxVal);
    
40.     }
    
41.     return 0;
    
42. }
    

复制代码

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数组的变化

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. const std::vector<int> get_element(const std::vector<int> &data, const std::vector<bool> &flag) {
   
5.     std::vector<int> result;
   
6.     if(data.size() != flag.size()) throw "data.size() != flag.size()";
   
7.     for(size_t i = 0; i < flag.size(); ++i) if(flag[i]) result.push_back(data[i]);
   
8.     return result;
   
9. }
   
10. 
    
11. bool change_flag(std::vector<bool> &flag) {
    
12.     for(size_t i = 0; i < flag.size() - 1; ++i) {
    
13.         if(flag[i] && !flag[i + 1]) {
    
14.             flag[i] = false; flag[i + 1] = true;
    
15.             size_t count = 0;
    
16.             for(size_t j = 0; j < i; ++j) if(flag[j]) ++count;
    
17.             for(size_t j = 0; j < i; ++j) flag[j] = false;
    
18.             for(size_t j = 0; j < count; ++j) flag[j] = true;
    
19.             return true;
    
20.         }
    
21.     }
    
22.     return false;
    
23. }
    
24. 
    
25. const std::vector<std::vector<int>> combine(const std::vector<int> &data, size_t n) {
    
26.     std::vector<std::vector<int>> result;
    
27.     std::vector<bool> flag(data.size(), false);
    
28.     for(size_t i = 0; i < n; ++i) flag[i] = true;
    
29.     result.push_back(get_element(data, flag));
    
30.     while(change_flag(flag)) result.push_back(get_element(data, flag));
    
31.     return result;
    
32. }
    
33. 
    
34. void filter(std::vector<std::vector<int>> &data) {
    
35.     for(size_t i = 0; i < data.size(); ++i) {
    
36.         for(size_t j = 0; j < data[i].size() - 1; ++j) {
    
37.             if(data[i][j] > data[i][j + 1]) {
    
38.                 data.erase(data.begin() + i);
    
39.                 --i; break;
    
40.             }
    
41.         }
    
42.     }
    
43. }
    
44. 
    
45. const std::vector<std::vector<int>> get_subsequence(const std::vector<int> &data) {
    
46.     std::vector<std::vector<int>> result;
    
47.     for(size_t i = 0; i <data.size(); ++i) {
    
48.         std::vector<std::vector<int>> v = combine(data, i + 1);
    
49.         filter(v); for(const auto &j: v) result.push_back(j);
    
50.     }
    
51.     return result;
    
52. }
    
53. 
    
54. size_t max(const std::vector<std::vector<int>> &data) {
    
55.     size_t max_value = 0;
    
56.     for(const auto &iter: data) {
    
57.         size_t sum = 0;
    
58.         for(const auto &e: iter) sum += e;
    
59.         if(max_value < sum) max_value = sum;
    
60.     }
    
61.     return max_value;
    
62. }
    
63. 
    
64. int main() {
    
65.     std::cout << "请输入: ";
    
66.     size_t size;
    
67.     std::cin >> size;
    
68.     std::vector<int> data;
    
69.     for(size_t i = 0; i < size; ++i) {
    
70.         size_t e;
    
71.         std::cin >> e;
    
72.         data.push_back(e);
    
73.     }
    
74.     std::cout << max(get_subsequence(data)) << std::endl;
    
75.     return 0;
    
76. }
    

复制代码

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
因为这题用穷举会超时（这是我相信的）

嗯