本文主要是介绍【Codeforces Round 323 (Div 2)D】【暴力 脑洞 插入贡献思想】Once Again... 循环节重复T次后的LIS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=1e4+1e3,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int n,m,T;
int a[N],f[N];
int main()
{while(~scanf("%d%d",&n,&T)){int cir=min(100,T);int len=cir*n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);int ans=0;for(int i=1;i<=len;i++){if(i>n)a[i]=a[i-n];f[i]=1;int st=max(1,i-n);for(int j=st;j<i;j++)if(a[j]<=a[i])gmax(f[i],f[j]+1);gmax(ans,f[i]);}if(T>cir){int now=0;for(int i=len+1;i<=len+n;i++){a[i]=a[i-n];f[i]=1;for(int j=i-n;j<i;j++)if(a[j]<=a[i])gmax(f[i],f[j]+1);gmax(now,f[i]);}int dif=now-ans;ans+=(T-cir)*dif;}printf("%d\n",ans);}return 0;
}
/*
【trick&&吐槽】
1，形成插入思想。用暴力思维解决问题。
2，注意细节。【题意】
给你一个长度为n（[1,100]）的数列，这个数列形成了T次，即总共有n*T个数出现。
对于位置i（i>n），有a[i]=a[i-n]。
让你输出数列a[]的最长单调不下降子序列的长度【类型】
脑洞【分析】
这题我观察到，因为数的个数最多才只有n个，所以就算数列重复的次数很大，形成的递增的数的个数也不过只有n。
于是我们会有大量相等的LIS元素出现。基于这个观察到的性质，我一开始选择的做法是，向前枚举一个循环节，向后枚举一个循环节，两个循环节求出LIS，然后枚举中间字符为相同，
三部分拼接起来更新答案。但是这种做法是错误的。
比如数据9 10 11 12 5 6 7 8 1 2 3 4
于是我们发现，形成递增的循环节数量不止只有最前一个最后一个，而可能是很多个。
于是这里要怎么办？方法一，枚举前循环节数量，枚举后循环节数量，然后再做拼接。
然而这个方法的时间复杂度巨大，实现起来细节众多，于是比赛的时候我就误入歧途，连这么水的一道题都没有做出来TwT方法二，抓主要矛盾！
这道题的n只有100，而循环节的数量可达1e7.
如果循环节的数量只有100，那么我们甚至可以直接求LIS，
于是问题转变为两部分——
1，T<=100，这时可以直接暴力
2，T>100时，我们再新增一个循环节，这个循环节对之前LIS的影响，一定是这个循环节以平的形式插入到之前的LIS数列中。
于是我们求出这时插入新增循环的贡献量，而之后每次插入新增循环节，插入新增数量*单一贡献就是对答案的贡献。由此战胜答案即可。至于LIS，我们用O（(100n)^2）求也可，用O（(100n)log(100n)）也可。【时间复杂度&&优化】
O（(100n)^2）
O（(100n)log(100n)）【数据】
12 3
9 10 11 12 5 6 7 8 1 2 3 4 */这篇关于【Codeforces Round 323 (Div 2)D】【暴力 脑洞 插入贡献思想】Once Again... 循环节重复T次后的LIS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
