POJ1836 Alignment(LIS)

分析：

从左向右求一遍LIS，再从右向左求一遍LIS，最后一综合，就OK了。

注意：

有一种特殊情况（详见discuss)：

8

3 4 5 1 2 5 4 3

答案是：2

AC代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

using namespace std;

const int maxn =  + ;

const double INF = 1e100;

double a[maxn];

int d1[maxn], d2[maxn];\

int main() {

    int n;

//    freopen("my.txt", "r", stdin);

    while(cin>>n) {

        for(int i=; i<n; i++) cin>>a[i];

        d1[] = ;

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

            int m = ;

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

                if(a[j] < a[i] && m < d1[j]) m = d1[j];

            }

            d1[i] = m+;

        }

        d2[n-] = ;

        for(int i=n-; i>=; i--) {

            int m = ;

            for(int j=n-; j>i; j--) {

                if(a[j] < a[i] && m < d2[j]) m = d2[j];

            }

            d2[i] = m+;

        }

        int ans = ;

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

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

                ans = max(ans, d1[i]+d2[j]);

            }

        }

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

    }

    return ;

}

加个二分写法，在《训练指南》上学的二分写法，解题思想一样，写法不一样而已。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

using namespace std;

const int maxn =  + ;

const double INF = 1e100;

double a[maxn];

int d1[maxn], d2[maxn];

double G[maxn];

int main() {

    int n;

    //freopen("my.txt", "r", stdin);

    while(cin>>n) {

        for(int i=; i<n; i++) cin>>a[i];

        for(int i=; i<=n; i++) G[i] = INF;

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

            int k = lower_bound(G+, G+n+, a[i]) - G;

            G[k] = a[i];

            d1[i] = k;

        }

        for(int i=; i<=n; i++) G[i] = INF;

        for(int i=n-; i>=; i--) {

            int k = lower_bound(G+, G+n+, a[i]) - G;

            G[k] = a[i];

            d2[i] = k;

        }

        int ans = ;

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

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

                ans = max(ans, d1[i]+d2[j]);

            }

        }

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

    }

    return ;

}

巴特西

POJ1836 Alignment(LIS)

最新文章

热门文章