HDU 1257 最少拦截系统（最长上升子序列）

题意：

给定n个数，然后要求看看有多少对不上升子序列。

分析：

求出最长上升子序列，那么整个序列中LIS外的数都会在前面找到一个比自己大的数，所以不上升子序列最多有最长上升子序列个数个。

关于求LIS，下列有两种DP算法

O（n²）

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<cmath>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

int a[ + ], dp[ + ], n;

int main()

{

/*  求出最长上升子序列， 那么整个序列中LIS外的数都会在前面找到一个比自己大的数*/

    while(cin >> n){

        rep(i,,n) cin >> a[i];

        int ans = -;

        rep(i,,n){

            dp[i] = ;

            rep(j,,i){

                if(a[j] < a[i]) dp[i] = max(dp[i] , dp[j] + );

                ans = max(ans, dp[i]);

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

二分思想，设置一个栈，扫描一遍序列，每次将大于栈顶元素的入栈，小于栈顶元素的在栈中找到一个刚好大于等于该元素的替换掉，复杂度O（nlogn）

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<cmath>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

int a[ + ], dp[ + ], n;

int main()

{

/*  求出最长上升子序列， 那么整个序列中LIS外的数都会在前面找到一个比自己大的数*/

    while(cin >> n){

        rep(i,,n) {

            cin >> a[i];

            dp[i] = 1e9;

        }

        for(int i = ; i < n; i++){

            *lower_bound(dp, dp+n, a[i]) = a[i]; //每次找到一个>= a[i]的替换掉

        }

        printf("%d\n", lower_bound(dp,dp+n,1e9) - dp); //找到第一个INF的地址减去首地址就是最大子序列的长度；

    }

巴特西

HDU 1257 最少拦截系统（最长上升子序列）

题意：

分析：

最新文章

热门文章