time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array of positive integers a1, a2, …, an × T of length n × T. We know that for any i > n it is true that ai = ai - 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 ≤ 107). The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ 300).
Output
Print a single number — the length of a sought sequence.
Examples
input
4 3
3 1 4 2
output
5
Note
The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence.
【题目链接】:http://codeforces.com/contest/583/problem/D
【题解】
每次都选出现最多个数的数?
3 4 1 2
难道你要随便选一个数?
显然
12 3 4 4 4 4 4…
更优
其中1、2是在a[1..n]中选的,3、4是在a[n+1..2n]中选的;
当然你也可以这样选
1 2 2 2 2 ….. 2 2 3 4
或
1 2 3 3 3 3 3 3 …. 3 3 3 4
所以不能直接选出现次数最多的数字;
还得用一些“聪明的技巧”
聪明的技巧当然就是DP了；
可以考虑
5 6 3 4 1 2
可以看到；
我们第一次会选 12
第二次会选 3 4
第三次会选 5 6
所以最少把原序列复制6/2==3次才行;
在这n*(n/2)个数字里面进行DP;
那
6 5 4 3 2 1咋办？
这种情况我们完全不用想；
直接随便取一个数字就行了;
然后每次都选那个数字;
又例如
5 6 4 3 2 1
则第一次选5 6 其余的都选6就好：
然后复制6/2==3次完全够了
则进行DP的时候会选出
5 6 6 6
剩余的全部填6;
又例如
5 5 6 4 3 2 1
进行6/2==3次DP
会选出
5 5 5 5 5 5 6
其他的每次都选两次5选在最前面就好;
即我们选择的出现次数最多的数字是肯定有地方放的；所以不用担心;
总结一下就是
把n个数字复制n/2次;然后对这n*(n/2)个数字进行DP;求出这n*(n/2)个数字的最长不下降子序列；
(求n*(n/2)个数字的最长不下降子序列的时候只要往前找n个位置更新f[i]就可以了,具体的自己想，很简单的);
然后在初始的n个数字中选择出现次数最多的数字的次数key;
答案就是DP算出来的最长+(t-(n/2))*key
如果n==1要特判下,不然会搞笑.
【完整代码】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
int n,t,a[MAXN],lim,f[MAXN],ans = 0,mf = 0,b[350] = {0};
int main()
{
//freopen("F:\\rush.txt","r",stdin);
scanf("%d%d",&n,&t);
for (int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
mf = max(mf,b[a[i]]);
}
lim = n*min(n/2,t);
if (n==1)
lim = n;
for (int i = n+1;i <= lim;i++)
a[i] = a[i-n];
for (int i = 1;i <= lim;i++)
{
f[i] = 1;
for (int j = 1;j <= i-1;j++)//faster algorithm ->for (int j = max(1,i-n);j<=i-1;j++)
if (a[j] <= a[i])
f[i] = max(f[i],f[j]+1);
ans = max(ans,f[i]);
}
if (n==1)
n++;
if (t <= (n/2))
printf("%d\n",ans);
else
printf("%d\n",ans+(t-(n/2))*mf);
return 0;
}