Codeforces Round #323 (Div. 2) Once Again... CodeForces

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

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.

　　其实想了好久都不明白网上有人说是插空是怎么回事，现在也不明白。先记下，看以后会不会懂。。。只能泛泛的理解长度为n的序列重复n次应该会出现比较特殊的情况，比如‘循环’什么的。在怎么循环这个重复的序列也只有n个不同的数。t比n大很多，t<=n时直接做不会超时，t很大时，只求到重复n次的lis。之后加上后面原来数列里面出现次数最多的数的次数*(t-n)。可以想象，一个数在原序列里面出现次数越多，最长不下降数列里面它出现的几率和次数应该也是最多的。

实现过程中用到upper_bound()函数，它是求一个数的上界位置，就是比要求的数大的第一个位置，注意这里是大于不是大于等于。比如a[5]={1,2,2,2,5},upper_bound(a,a+5,2)-a=4.（严格来说返回的是数组编号地址）就是比2大的第一个位置下标为4。所以当数组里所有元素都小于等于给定的key的话，它会返回数组最后一个元素的下一个位置的下标，即upper_bound(a,a+5,5)-a=5。而lower_bound()函数是求大于等于当前值的第一个位置，所以lower_bound(a,a+5,2)-a=1，即第一次出现大于等于2的位置下标为1。

非下降子序列和递增有一点的不同就是允许重复。所以用upper_bound()求当前元素的下一个位置，再更新。知道upper_bound()的作用代码就好理解了：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN = 1e4 + 10;
 6 int dp[MAXN];
 7 int num[MAXN], a[110];
 8 int re[330];
 9 
10 int main()
11 {
12     int n, t;
13     int maxncnt = 0;
14     memset(re, 0, sizeof(re));
15     memset(dp, 0, sizeof(dp));
16     scanf("%d%d", &n, &t);
17     for (int i = 0; i < n; i++) {
18         scanf("%d", &a[i]);
19         re[a[i]]++;
20         if (re[a[i]] > maxncnt) maxncnt = re[a[i]];
21     }
22     int cnt = 0;
23     for (int i = 0; i < min(n, t); i++) {
24         for (int j = 0; j < n; j++)
25             num[cnt++] = a[j];
26     }
27     int val = 0;
28     for (int i = 0; i < cnt; i++) {
29         int pos = upper_bound(dp, dp + val, num[i]) - dp;
30         if (pos == val) dp[val++] = num[i];
31         else dp[pos] = num[i];
32     }
33     if (t > n) val += (t - n)*maxncnt;
34     printf("%d
", val);
35     return 0;
36 }

求非减lis处代码还可以仿照lis求法做下小改动。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN = 1e4 + 10;
 6 int dp[MAXN];
 7 int num[MAXN], a[110];
 8 int re[330],val;
 9 
10 int main()
11 {
12     int n, t;
13     int maxncnt = 0;
14     memset(re, 0, sizeof(re));
15     memset(dp, 0, sizeof(dp));
16     scanf("%d%d", &n, &t);
17     for (int i = 0; i < n; i++) {
18         scanf("%d", &a[i]);
19         re[a[i]]++;
20         if (re[a[i]] > maxncnt) maxncnt = re[a[i]];
21     }
22     int cnt = 0; 
23     for (int i = 0; i < min(n, t); i++) {
24         for (int j = 0; j < n; j++) {
25             num[cnt++] = a[j];
26         }
27     }
28     int val = 1;
29     dp[0] = num[0];
30     for (int i = 1; i < cnt; i++) {
31         if (num[i] >= dp[val - 1]) dp[val++] = num[i];
32         else
33         {
34             int pos = upper_bound(dp, dp + val, num[i]) - dp;
35             dp[pos] = num[i];
36         }
37     }
38     if (t > n) val += (t - n)*maxncnt;
39     printf("%d
", val);
40     return 0;
41 }

View Code

我非作死想要自己实现类似upper_bounder()的作用自己写二分，怎么写都不对，但还是有人会写。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN = 1e4 + 10;
 6 int dp[MAXN],num[MAXN];
 7 int a[110];
 8 int re[330], val;
 9 
10 int binary_search(int i)
11 {
12     int left, right, mid;
13     left = 1, right = val;
14     while (left<right)
15     {
16         mid = (left + right) >> 1;
17         if (dp[mid] > num[i]) right = mid;
18         else left = mid + 1;
19     }
20     return left;
21 }
22 
23 int main()
24 {
25     int n, t;
26     int maxncnt = 0;
27     memset(re, 0, sizeof(re));
28     memset(dp, 0, sizeof(dp));
29     scanf("%d%d", &n, &t);
30     for (int i = 1; i <= n; i++) {
31         scanf("%d", &a[i]);
32         re[a[i]]++;
33         if (re[a[i]] > maxncnt) maxncnt = re[a[i]];
34     }
35     int cnt = 1;
36     for (int i = 1; i <= min(n, t); i++) {
37         for (int j = 1; j <= n; j++)
38             num[cnt++] = a[j];
39     }
40     val = 1;
41     dp[1] = num[1];
42     for (int i = 2; i <= cnt; i++) {
43         if (num[i] >= dp[val])
44             dp[++val] = num[i];
45         else {
46             int pos = binary_search(i);
47             dp[pos] = num[i];
48         }
49     }
50     printf("%d
", val + maxncnt*(t - min(n, t)));
51     return 0;
52 }

另一种二分写法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<map>
 6 #include<algorithm>
 7 using namespace std;
 8 int a[310];
 9 int s[10010];
10 int m[310];
11 
12 int main()
13 {
14     int n,T;
15     scanf("%d%d",&n,&T);
16     memset(m,0,sizeof(m));
17     int ansm=0;
18     for(int i=0;i<n;i++){
19         scanf("%d",a+i);
20         m[a[i]]++;
21         ansm=max(m[a[i]],ansm);
22     }
23     int top=0;
24     for(int i=0;i<min(n,T);i++){
25         for(int j=0;j<n;j++){
26             if(top==0||a[j]>=s[top-1]){
27                 s[top]=a[j];
28                 top++;
29             }else{
30                 int l=0,r=top-1;
31                 int ans=r;
32                 while(l<=r){
33                     int mid=(l+r)>>1;
34                     if(s[mid]>a[j]){
35                         ans=mid;
36                         r=mid-1;
37                     }else{
38                         l=mid+1;
39                     }
40                 }
41                 s[ans]=a[j];
42             }
43         }
44     }
45     printf("%d
",top+ansm*(T-min(n,T)));
46     return 0;
47 }

View Code