链接:
题意:
给你一个长度为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 mapcnt;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 }