若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1664: Longest Ordered Subsequence

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,133

题目描述

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, the 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 of this sequence 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.

输入

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

输出

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

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

样例输入

1

7
1 7 3 5 9 4 8

样例输出

4

参考代码

#include <stdio.h>  
#define N 1001  
int s[N], d[N];
int main() 
{
    int t, i, j, n, ans;
    scanf("%d", &t);
    while(t--) 
    {
        ans = 0;
        scanf("%d", &n);
        for (i=0; i<n; i++) 
        {
            scanf("%d", &s[i]);
            d[i] = 1;
            for (j=0; j<i; j++)  
                            if(s[j] < s[i] && d[j] + 1 > d[i])  
                                d[i] = d[j] + 1;
            if(d[i] > ans)  
                            ans = d[i];
        }
        printf("%dn", ans);  
        if(t)printf("n");  
    }  
    return 0;  
}

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist