Maxim and Increasing Subsequence
首先,我们可以发现,当这个重复次数很大的时候,答案就等于序列中出现的不同权值个数。实际上,这个“很大”就可以被当作“大于等于不同权值个数”。
不同权值个数实际上是 \(\min(n,m)\) 级别的,其中 \(n\) 是序列长度,\(m\) 是序列最大值。因此直接特判掉即可。
我们考虑暴力 DP,设 \(f_{i,j}\) 表明现在跑到序列中的第 \(i\) 个位置,且所有最后一个数小于等于 \(j\) 的 LIS 的长度的最大值。假如我们直接暴力扫过 DP 数组更新的话,最多最多更新 \(\min(n,m)^2\) 次,即最终把DP数组中所有数全都更新到最大值。而又有 \(n\times m\leq2\times10^7\),所以我们最终会发现复杂度最大只有 \(2\times10^7\)。时限 6 秒,轻松跑过。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int T,n,lim,m;
int a[N],f[N];
vector<int>v;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T>>n>>lim>>m;
while(T--){
v.clear();
for(int i=0;i<n;i++){
cin>>a[i];
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
if(v.size()<=m){printf("%d\n",v.size());continue;}
for(int i=0;i<n;i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
for(int i=1;i<=v.size();i++) f[i]=0;
for(int i=0;i<n*m;i++){
int now=f[a[i%n]-1]+1;
for(int j=a[i%n];j<=v.size();j++){
if(f[j]<now) f[j]=now;
else break;
}
if(f[v.size()]==v.size()) break;
}
cout<<f[v.size()]<<'\n';
}
return 0;
}
- 题解 Subsequence Increasing Maxim 261D题解subsequence increasing maxim 题解calculator maxim 261e 题解subsequence increasing longest longest-increasing-subsequence longest-increasing-subsequence subsequence increasing subsequence codeforces increasing almost subsequence increasing longest 568e subsequence increasing almost 1817a 题解261f abc 题解 数组subsequences increasing