POJ 2533-Longest Ordered Subsequence(DP)

POJ 2533-Longest Ordered Subsequence(DP)

大家好,又见面了,我是全栈君。

Longest Ordered Subsequence
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 34454   Accepted: 15135

Description

A numeric sequence of 
ai is ordered if 
a1 < 
a2 < … < 
aN. Let the subsequence of the given numeric sequence (
a1
a2, …, 
aN) be any sequence (
ai1
ai2, …, 
aiK), where 1 <= 
i1 < 
i2 < … < 
iK <= 
N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence – N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer – the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4
最长上升子序列。

。orz 傻逼竟然直接把dp[n]输出了 后来wa了一时还没反应过来。。

dp[i]代表以i为结尾的最长上升子序列的长度,but dp[n]不一定最长。。事实上整个dp数组就是无序的了。

能够sort后输出

O(n*n)渣比写法
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 1010
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ?

(x) : (y) )#define min(x,y) ( ((x) > (y)) ? (y) : (x) )using namespace std;int n,dp[maxn],a[maxn];void solve(){ for(int i=2;i<=n;i++) for(int j=1;j<i;j++) if(a[i]>a[j]&&dp[i]<=dp[j]) dp[i]=dp[j]+1; sort(dp+1,dp+n+1); printf("%d\n",dp[n]);}int main(){ while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { dp[i]=1; scanf("%d",&a[i]); } solve(); } return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116655.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 数据结构和算法—-单向链表

    数据结构和算法—-单向链表

  • 浅谈IOC–说清楚IOC是什么

    浅谈IOC–说清楚IOC是什么转载自:http://www.cnblogs.com/DebugLZQ/archive/2013/06/05/3107957.html1.IOC的理论背景2.什么是IOC3.IOC也叫依赖注入(DI)4.IOC的优缺点5.IOC容器的技术剖析6.IOC容器的一些产品7.参考博文本文旨在用语言(非代码)说清楚IOC到底是什么,没有什么高深的技术,园中的老牛、大虾们看到这里可以绕行了,以免浪费您宝贵的…

  • SAP QAS数据增长空间太快

    SAP QAS数据增长空间太快背景:我们是在一台数据库上删除另外的一台数据库上的大量数据,运用的crontab+linuxshell+rman,然后生产了大量的日志。解决方法清除以下的日志deletearchivelog.sh脚本exportORACLE_SID=QASexportORACLE_BASE=/oracleexportORACLE_HOME=/oracle/QAS/112_64/oracle/QAS/112_64/bin/rmantarget/<<EOFrun{cro

  • lib vs 生成pdb_pdb文件 VS c++编译[通俗易懂]

    lib vs 生成pdb_pdb文件 VS c++编译[通俗易懂]使用VS-debug模式下编译的时候,经常出现以下问题:’Dlib.exe'(Win32):Loaded’D:\c++\Dlib\x64\Debug\Dlib.exe’.Symbolsloaded.’Dlib.exe'(Win32):Loaded’C:\Windows\System32\ntdll.dll’.CannotfindoropenthePDBfile.’Dl…

  • IDEA- idea代码调试debug

    IDEA有很多的快捷键,下面整理Debug的快捷键,方便自己使用!

  • TraCI4Matlab的安装教程「建议收藏」

    TraCI4Matlab的安装使用教程安装1、下载安装Sumo2、下载安装TraCI4Matlab3、设置环境变量4、添加traci4matlab.jar路径5、将javaclasspath.txt复制至Matlab路径中6、配置Matlab路径安装Matlab有联合Sumo的插件traci4Matlab,网上还没有中文版的安装教程,走过的弯路,后来研究者尽可能少走。1、下载安装Sumo百度搜索sumo,点击进入官网,如图1:根据自己电脑系统进行下载:软件占的空间较少,按照提示安装完成即可:2

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号