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

男娘i 2022-01-16 11:35 199阅读 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 条评论，199人围观）

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

相关阅读

相关信奥赛一本通1149：最长单词2

【题目描述】一个以‘.’结尾的简单英文句子，单词之间用空格分隔，没有缩写形式和其它特殊形式。【输入】一个以‘.’结尾的简单英文句子（长度不超过500），单词

落日映苍穹つ/ 2023年09月25日 17:12/ 0 赞/ 14 阅读

相关信奥赛一本通2036：【例5.3】开关门

【题目描述】宾馆里有n(2≤n≤1000)个房间，从1∼n编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相反处理”，第三个服务员把

ゝ一纸荒年。/ 2023年09月23日 21:26/ 0 赞/ 2 阅读

相关动态规划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 阅读

相关动态规划２：最长不下降子序列－－连续序列＋不连续序列

//最长不下降子序列－－连续+不连续 include <cstdio> include "vector" include "algor

梦里梦外;/ 2023年07月09日 02:01/ 0 赞/ 19 阅读

相关 C++信息学奥赛一本通（T1409：判决素数个数）

【题目描述】输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。【输入】两个整数X和Y（1≤X,Y≤105）。【输出】输出一个整数，表示X

骑猪看日落/ 2023年02月27日 10:49/ 0 赞/ 16 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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