【洛谷_CF261D】Maxim and Increasing Subsequence
程序员文章站
2024-03-02 23:26:34
...
Maxim and Increasing Subsequence
题目大意:(原文为英文,以下为大意内容)
给定一个序列,重复 t 遍后求最长上升子序列(严格单调)
给定 k 组数据 ,每组数据有相同的 n ,maxb 和 t 。分别表示元素的个数、元素中最大的数和重复几遍
样例输入
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;
}
}
上一篇: python处理按钮消息的实例详解