一本通 1259：【例9.3】求最长不下降序列

- 日理万妓 2021-12-15 14:49 258阅读 0赞

# [求最长不下降序列][Link 1] #

状态转移方程：if(ai>aj) fi = max(fi, fj+1)

#include <iostream>
    #include <cstdio>
    using namespace std;
    //Mystery_Sky
    //
    #define M 1000
    int f[M], a[M], n, t=0;
    int ans, ans_num, next[M], ans_xu[M];
    int main() {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), f[i] = 1;
        for(int i = 2; i <= n; i++)
            for(int j = 1; j < i; j++) 
                if(a[i] >= a[j]) { //坑点 
                    if(f[j] + 1 > f[i]) {
                        f[i] = f[j] + 1;
                        next[i] = j;
                    } 
                }
        for(int i = 1; i <= n; i++) {
            if(f[i] > ans) {
                ans = f[i];
                ans_num = i;
            }
        }
        printf("max=%d\n", ans);
        while(ans_num) {
            ans_xu[++t] = a[ans_num];
            ans_num = next[ans_num];
        }
        for(int i = t; i >= 1; i--) printf("%d ", ans_xu[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/Benjamin-cpp/p/10786305.html

[Link 1]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1259

发表评论取消回复

表情：

评论列表（有 0 条评论，258人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划3-例9.3最长不下降子序列

例9.3最长不下降子序列 //设有由n个不相同的整数组成的数列，记为：b(1),b(2)...b(n)且b(i)<>b(j)(i<>j), //若存在i1<i2<i3<

港控/mmm°/ 2023年07月11日 11:27/ 0 赞/ 9 阅读

相关最长不下降子序列

Problem B: So easy Time Limit: 2 Sec Memory Limit: 128 MB Submit: 34 Solved: 11

忘是亡心i/ 2022年07月15日 10:17/ 0 赞/ 177 阅读

相关最长不下降子序列

/开辟一个堆栈数组stack[]，每次取栈顶元素top和读到的元素temp做比较，如果temp>top则将temp入栈，如果temp<=top则二分查找栈中的

绝地灬酷狼/ 2022年06月16日 13:45/ 0 赞/ 230 阅读

相关求最长不下降序列并输出序列（动态规划）

【例9.3】求最长不下降序列时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】设有由n(1<=n<=200)个不相同的整数组成

向右看齐/ 2022年06月08日 07:12/ 0 赞/ 173 阅读

相关最长上升子序列，最长不下降子序列

最长上升子序列 include<iostream> include<cstdio> using namespace std; const in

深藏阁楼爱情的钟/ 2022年05月13日 22:55/ 0 赞/ 303 阅读

相关最长不下降子序列

定义：设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 例如3，18，7，14，10，12，23，41，1

悠悠/ 2022年04月15日 05:42/ 0 赞/ 204 阅读

相关最长不下降子序列自实现

在学习动态规划过程中,下面是我自己实现的LIS,时间复杂度O(n),不知道正确与否,先记下来 include <iostream> include <algo

水深无声/ 2022年03月19日 08:08/ 0 赞/ 244 阅读

相关【例3】求最长不下降序列(动态规划） --《信息学奥赛一本通》

/ 【例3】求最长不下降序列(动态规划） --《信息学奥赛一本通》 [http://ybt.ssoier.cn:8088/problem\_show.php?pid=1

男娘i/ 2022年01月16日 11:35/ 0 赞/ 198 阅读

相关一本通 1259：【例9.3】求最长不下降序列

[求最长不下降序列][Link 1] 状态转移方程：if(ai>aj) fi = max(fi, fj+1) include <iostream> in

- 日理万妓/ 2021年12月15日 14:49/ 0 赞/ 259 阅读

相关一本通 1281：最长上升子序列

[最长上升子序列][Link 1] include <iostream> include <cstdio> using namespace std

た入场券/ 2021年12月15日 14:49/ 0 赞/ 254 阅读