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

链接：

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

题意：

给你一个长度为n的序列，复制T次，求最长不下降子序列

题解：

n最大为100，所以我们可以计算出n*n的最长不下降子序列长度，如果T>n，

我们会发现中间一定会有重复的，重复的就是a数组中出现次数最多的数字

代码：

31 int n, T, a[110];
32 int dp[10010];
33 
34 int main() {
35     ios::sync_with_stdio(false), cin.tie(0);
36     cin >> n >> T;
37     map<int, int> cnt;
38     int Max = 0;
39     rep(i, 0, n) {
40         cin >> a[i];
41         cnt[a[i]]++;
42         Max = max(Max, cnt[a[i]]);
43     }
44     memset(dp, 0x3f, sizeof(dp));
45     if (T < 100) {
46         VI v;
47         rep(i, 0, T) rep(j, 0, n) v.pb(a[j]);
48         n *= T;
49         rep(i, 0, n) *upper_bound(dp, dp + n, v[i]) = v[i];
50         cout << lower_bound(dp, dp + n, INF) - dp << endl;
51     }
52     else {
53         VI v;
54         rep(i, 0, 100) rep(j, 0, n) v.pb(a[j]);55         n *= 100;
56         rep(i, 0, n) *upper_bound(dp, dp + n, v[i]) = v[i];
57         cout << (lower_bound(dp, dp + n, INF) - dp) + Max*(T - 100) << endl;
58     }
59     return 0;
60 }