欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷_CF261D】Maxim and Increasing Subsequence

程序员文章站 2024-03-02 23:26:34
...

Maxim and Increasing Subsequence


题目大意:(原文为英文,以下为大意内容)

给定一个序列,重复 t 遍后求最长上升子序列(严格单调)

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

样例输入

3 3 5 2
3 2 1
1 2 3
2 3 1

样例输出

2
3
3

解题思路

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

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

#include<iostream>
#include<cstdio>
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<<sum<<endl;
			continue; 
		}
		for(int i=1;i<=100007;i++)
			f[i]=tree[i]=0;
		int ans=0;
		for(int i=1;i<=t;i++)
			for(int j=1;j<=n;j++)
			{
				int x=find(a[j]-1)+1;
				if(x>f[j])
				{
					f[j]=x;
					ans=max(ans,x);
					change(a[j],x);
				}
				if(ans>=sum)
					break;
			}
		cout<<ans<<endl;
	}
}