题意:给你一个序列n,有T个连续这样的序列,求最长不下降子序列的长度;
思路:发现T很大,n很小对吧,
显然中间肯定是有一段是连续的相同的数对吧;
开始想前面取一个LIS,最后取一个LIS,中间相同,数量最多的那个数;
这个做法错误,可能后面的前一个还能多取;
如果T<=n比较小,我们只需要暴力跑LIS即可;
现在讨论T>n的情况;
然后发现只有n个数,也就是说最后的LIS最多只有n段不同的数;
也就是说我们只需要拿出n段序列出来,跑LIS即可;
因为最多n段,然后取完n段,多余的可以从中间插入;
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define mk make_pair #define eps 1e-7 #define bug(x) cout<<"bug"<<x<<endl; const int N=1e5+10,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=1000000007; /// 数组大小 int arr[N],ans[N],len; int binary_search(int i) { int left,right,mid; left=0,right=len; while(left<right) { mid = left+(right-left)/2; if(ans[mid]>arr[i]) right=mid; else left=mid+1; } return left; } int LIS(int p) { ans[1] = arr[1]; len=1; for(int i=2; i<=p; ++i) { if(arr[i]>=ans[len]) ans[++len]=arr[i]; else { int pos=binary_search(i); ans[pos] = arr[i]; } } return len; } int flag[N]; int main() { int n,T,maxx=0; scanf("%d%d",&n,&T); for(int i=1;i<=n;i++) scanf("%d",&arr[i]),flag[arr[i]]++,maxx=max(maxx,flag[arr[i]]); for(int i=1;i<n;i++) for(int j=1;j<=n;j++) arr[i*n+j]=arr[j]; if(n>=T)printf("%d ",LIS(n*T)); else printf("%d ",LIS(n*n)+maxx*(T-n)); return 0; }