LCIS HDOJ 4512 吉哥系列故事——完美队形I

题目传送门

题意：中文题面

分析：LCIS应用：设置b[]为a[]的反转，然后LCIS，若相等的是自己本身，则+1， 否则+2

代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN = 2e2 + 10;

const int INF = 0x3f3f3f3f;

int a[MAXN], b[MAXN];

int dp[MAXN][MAXN];

int n;

int LCIS(void)

{

    int k = 0;    int ans = 0;

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

    {

        k = 0;

        for (int j=1; j<=n-i+1; ++j)

        {

            dp[i][j] = dp[i-1][j];

            if (a[i] == b[j])

            {

                if (j != n - i + 1)

                {

                    if (dp[i][j] < dp[i][k] + 2)

                        dp[i][j] = dp[i][k] + 2;

                }

                else

                {

                    if (dp[i][j] < dp[i][k] + 1)

                        dp[i][j] = dp[i][k] + 1;

                }

            }

            else if (a[i] > b[j])

                if (dp[i][j] > dp[i][k])    k = j;

            if (ans < dp[i][j])    ans = dp[i][j];

        }

    }

    return ans;

}

int main(void)        //HDOJ 4512 吉哥系列故事——完美队形I

{

    //freopen ("HDOJ_4512.in", "r", stdin);

    int t;

    scanf ("%d", &t);

    while (t--)

    {

        scanf ("%d", &n);

        for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);

        for (int i=1; i<=n; ++i)    b[n-i+1] = a[i];

        memset (dp, 0, sizeof (dp));

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

    }

    return 0;

}