首页 > 其他 > 详细

最长上升子序列

时间:2017-08-19 12:13:59      阅读:274      评论:0      收藏:0      [点我收藏+]

合唱队形题

题目分析 :分别求最长上升和下降子序列。

题目分析 :这道题差不多是个水题了,不过我在做题的被误导了,虽然结果正确却超时了。我们用上升子序列的时间复杂度是:O(n*n);

题目收获 :需要对时间复杂和空间复杂度进行深刻的重新理解。

AC代码 :

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define maxn 105
using namespace std;
int d[maxn],b[maxn],num;
int pepo[maxn];

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d", &num);
    memset(d, 0, sizeof(d));
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= num; i++)
        scanf("%d", &pepo[i]);
    for (int i = 2; i <= num; i++)
        for (int j = 1; j < i; j++)
            if (pepo[i] > pepo[j])
                d[i] = max(d[i], d[j] + 1);
    for (int i = num - 1; i >= 1; i--)
        for (int j = num; j > i; j--)
            if (pepo[i] > pepo[j])
                b[i] = max(b[i], b[j] + 1);
    int ans = 0;
    for (int i = 1; i <= num; i++)
        ans = max(ans, b[i] + d[i]);
    printf("%d\n", num - ans - 1);
        return 0;
}

 

最长上升子序列

原文:http://www.cnblogs.com/7750-13/p/7395663.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!