Codeforces Round #323 (Div. 1) B. Once Again... 暴力-白红宇

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

阅读量：5318 次

发布时间：2019-06-14

本文共 1640 字，大约阅读时间需要 5 分钟。

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
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;#define maxn 3225020int 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=1;i<=n;i++) scanf("%d",&a[i]); if(t<=300) { int ans = 0; for(int i=1;i<=n;i++) for(int j=1;j
           
            =a[j]) lis[i]=max(lis[i],lis[j]+1); ans = max(lis[i],ans); } printf("%d\n",ans); return 0; } int k = 200; for(int i=1;i<=n;i++) dp2[a[i]]++; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) a[j*n+i] = a[i]; for(int i=1;i<=k*n;i++) { lis[i]=1; for(int j=1;j
            
             =a[j]) lis[i]=max(lis[i],lis[j]+1); dp1[a[i]] = max(dp1[a[i]],lis[i]); } memset(lis,0,sizeof(lis)); reverse(a+1,a+1+k*n); for(int i=1;i<=k*n;i++) { lis[i]=1; for(int j=1;j