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

男娘i 2022-01-16 11:35 183阅读 0赞

/  
*【例3】求最长不下降序列(动态规划） --《信息学奥赛一本通》  
[http://ybt.ssoier.cn:8088/problem\_show.php?pid=1259][http_ybt.ssoier.cn_8088_problem_show.php_pid_1259]*  
/  
\#include<iostream>  
using namespace std;  
int b\[2001\]\[10\];  
int main()  
\{  
int n,i,j,l,k;

//cout<<"input n:"<<endl;  
cin>>n;

//输入序列的初始值

for (i=1;i<=n;i++)  
\{  
cin>>b\[i\]\[1\];  
b\[i\]\[2\]=1;  
b\[i\]\[3\]=0;  
\}

//求最长不下降序列
    for (i=n-1;i>=1;i--)                      
    {
        l=0;
        k=0;
        for (j=i+1;j<=n;j++)
        {
            if ((b[j][1]>b[i][1])&&(b[j][2]>l))
            {
                l=b[j][2];
                k=j;
            }
        }
    
        if (l>0)
        {
           b[i][2]=l+1;
           b[i][3]=k;
        }  
     }
    
    k=1; 
    //求最长不下降序列的起始位置
    for (j=1;j<=n;j++)
    {
        if (b[j][2]>b[k][2]) k=j;
    }  
    
    //输出结果  
    cout<<"max="<<b[k][2]<<endl;  
    
    //输出最长不下降序列
    while (k!=0)                                
    {
        cout<<b[k][1]<<' ';
        //cout<<' '<<b[k][1];
        k=b[k][3];   
    } 
    
    return 0;

\}

转载于:https://blog.51cto.com/1443208/2397010

[http_ybt.ssoier.cn_8088_problem_show.php_pid_1259]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1259

发表评论取消回复

表情：

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

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

相关阅读

相关信奥赛一本通（2034：【例5.1】反序输出）

【题目描述】输入n个数,要求程序按输入时的逆序把这n个数打印出来，已知整数不超过100个。也就是说，按输入相反顺序打印这n个数。【输入】输入一行共有n个数，

朱雀/ 2023年09月23日 20:06/ 0 赞/ 110 阅读

相关 C++信息学奥赛一本通（T1413：确定进制）

【题目描述】 6×9=42对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13)× 9(13)= 42(13)，而 42(13)=4×131+2×130

冷不防/ 2023年02月27日 10:47/ 0 赞/ 5 阅读

相关最长不下降自序列（最长递增子序列）C++动态规划

题目：[http://www.kencoding.net/problem.php?id=1112][http_www.kencoding.net_problem.php_id_

你的名字/ 2022年08月29日 15:52/ 0 赞/ 187 阅读

相关【动态规划】求最长公共子序列

最长公共子串和最长公共子序列的区别： > 最长公共子串和最长公共子序列的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列

蔚落/ 2022年08月09日 00:59/ 0 赞/ 241 阅读

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

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

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

相关【谈谈】动态规划——求最长公共子序列

首先，我们要搞清楚所谓最长公共子序列的概念。不然很容易把它和最长公共子串混淆，两者区别是：子序列只需要字符保持相对顺序，并不要求像公共字串那样组成字符还需连续。问题：

素颜马尾好姑娘i/ 2022年01月31日 07:13/ 0 赞/ 237 阅读

相关求最长公共子序列（动态规划）

求最长公共子序列（动态规划）首先弄清楚，最长公共子串与最长公共子序列的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。比如说：A=\{

た入场券/ 2022年01月26日 03:11/ 0 赞/ 264 阅读

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

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

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

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

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

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

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

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

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