Codeforces Round #323 (Div. 1) B. Once Again... 暴力

B. Once Again...

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/582/problem/B

Description

You are given an array of positive integers a₁, a₂, ..., a_n × T of length n × T. We know that for any i > n it is true that a_i = a_i - n. Find the length of the longest non-decreasing sequence of the given array.

Input

The first line contains two space-separated integers: n, T (1 ≤ n ≤ 100, 1 ≤ T ≤ 10⁷). The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 300).

Output

Print a single number — the length of a sought sequence.

Sample Input

4 3
3 1 4 2

Sample Output

HINT

题意

给你一个n*t这么长的序列，然后求最长不递减序列

其中a[i+n]=a[i]

题解：

暴力，如果t<=300，我们就直接暴力求就好了

如果t>的话，我们就大胆猜测，中间肯定是连续选一个数

那么我们就预处理前面以a[i]开始的最长，和后面的以a[i]最长是啥就好了~

代码：

#include<iostream>

#include<stdio.h>

#include<queue>

#include<map>

#include<algorithm>

#include<string.h>

using namespace std;

#define maxn 3225020

int a[maxn];

int dp1[maxn];

int dp2[maxn];

int dp3[maxn];

int lis[maxn];

int main()

{

    int n,t;scanf("%d%d",&n,&t);

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

        scanf("%d",&a[i]);

    if(t<=)

    {

        int ans = ;

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

            for(int j=;j<t;j++)

                a[j*n+i] = a[i];

        for(int i=;i<=n*t;i++)

        {

            lis[i]=;

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

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

                    lis[i]=max(lis[i],lis[j]+);

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

        }

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

        return ;

    }

    int k = ;

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

        dp2[a[i]]++;

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

        for(int j=;j<=k;j++)

            a[j*n+i] = a[i];

    for(int i=;i<=k*n;i++)

    {

        lis[i]=;

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

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

                lis[i]=max(lis[i],lis[j]+);

        dp1[a[i]] = max(dp1[a[i]],lis[i]);

    }

    memset(lis,,sizeof(lis));

    reverse(a+,a++k*n);

    for(int i=;i<=k*n;i++)

    {

        lis[i]=;

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

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

                lis[i]=max(lis[i],lis[j]+);

        dp3[a[i]] = max(dp3[a[i]],lis[i]);

    }

    int ans = ;

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

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

            for(int m=j;m<=;m++)

                ans = max(dp1[i]+dp2[j]*(t-*k)+dp3[m],ans);

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

}

秒客网