本文共 932 字，大约阅读时间需要 3 分钟。

Maxim and Increasing Subsequence

题目大意：（原文为英文，以下为大意内容）

给定一个序列，重复 t 遍后求最长上升子序列（严格单调）

给定 k 组数据 ，每组数据有相同的 n ，maxb 和 t 。分别表示元素的个数、元素中最大的数和重复几遍

样例输入

3 3 5 23 2 11 2 32 3 1

样例输出

233

解题思路

如果序列中不同的元素小于等于重复的次数（ t ），那么答案就是不同元素的个数（ sum ）。

如果不大于重复的次数（ t ），那么我们用 f[i][j] 表示当前序列的最长子序列，但是我们要开滚动数组。我们可以用树状数组维护这个最长上升子序列，那么程序就出来了：

#include
   
    #include
    
     using namespace std;int k,n,maxb,t,sum;int a[100010],b[2000010];int f[100010],tree[100010];void change(int x,int y){   	for(;x<=maxb;x+=x&(-x))		tree[x]=max(tree[x],y);}int find(int x){   	int ans=0;	for(;x;x-=x&(-x))		ans=max(ans,tree[x]);	return ans;}int main(){   	cin>>k>>n>>maxb>>t;	while(k--)	{   		sum=0;		for(int i=1;i<=n;i++)		{   			scanf("%d",&a[i]);			if(b[a[i]]!=k+1)				sum++;			b[a[i]]=k+1;		}		if(t>=sum)		{   			cout<
     
      <
      
       f[j])				{   					f[j]=x;					ans=max(ans,x);					change(a[j],x);				}				if(ans>=sum)					break;			}		cout<
       
        <