【JZOJ4031】【CF261D】Maxim and Increasing Subsequence(DP)

时间:2021-02-01 14:58:40

Problem

  给定一个长度为n(≤)的序列b,复制t(≤)遍变成a数组,求a的最长上升子序列长度。多组数据。时限2s。

Input

  输入的第一行包括四个整数k,n,maxb,t。接下来k行中每一行包括n个整数b1,b2,…,bn。
  注意所有数列a的n,maxb,t是相等的,只有b是不同的。
  所有数字用一个空格分隔。
  其中,maxb=max(bi)。

Output

  输出k行,每行一个整数,分别表示k个数列a的最长上升子序列长度。按照输入顺序输出。

Hint

  对于30%的数据, n t 10 5
  对于100%的数据, 1 k 10 1 n , m a x b 10 5 1 t 10 9 n m a x b 2 10 7

Solution

  这道题我刚看还以为是什么高级的东西,比如说把它转化为矩阵乱乘一下,没想到就是个暴力……
  首先,设b数组中互不相同的数的个数为cnt,则若t≥cnt,则答案定为cnt,直接continue。原因很显然。(但我比赛时竟然没想到!!!
  那么我们就发现,真正有用的t≤min(n,maxb),所以可以直接模拟出a数组,而其长度≤ 2 10 7 。那样的话,直接对它求最长上升子序列即可。
  我们可以使用朴素的二分优化,这样时间复杂度即为 O ( k n t l o g ( c n t ) ) 。虽然n*t最大为 2 10 7 ,再乘个k,已满 2 10 8 ,再乘个log会T(其实能过)。不过有更优美的方法。
  我们可以枚举一个i,表示当前的最长不下降子序列的末个元素为a[i];设f[j]表示当j=a[i]时,前i个数的答案。那么一开始f全为0。每当你碰到一个a[i]时,它的答案len即为f[a[i]]+1,然后我们须将所有满足j>a[i]的f[j]都更新为max(f[j],len)。这样的话,我们每求到一个答案,都将其后面的值全部更新一遍,所以在枚举j的时候,只要碰到一个f[j]≥len就可以break了。
  上述的做法看似是 O ( k n t m a x n ) 的,但是实际上我们对于同一len,它最多只会把整个f数组的值变为len,而f数组也就maxb的大小;而总共有至多cnt个不同的len。所以:
  时间复杂度: O ( k c n t m a x b )

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100001
#define ll long long
#define fo(i,a,b) for(i=a;i<=b;i++)
int i,j,k,n,maxb,t,cnt,a,b[N],len,f[N],ans,x;
bool p[N];
int main()
{
    scanf("%d%d%d%d",&k,&n,&maxb,&t);
    for(;k;k--)
    {
        memset(p,0,sizeof p);
        fo(i,1,n)scanf("%d",&b[i]),p[b[i]]=1;
        cnt=0;
        fo(i,1,maxb)
            if(p[i])
                cnt++;
        if(t>cnt)
        {
            printf("%d\n",cnt);
            continue;   
        }

        memset(f,0,sizeof f);
        ans=x=0;

        fo(i,1,n*t)
        {
            if(++x>n)x=1;
            a=b[x];
            len=f[a]+1;
            ans=max(ans,len);
            fo(j,a+1,maxb)
                if(len>f[j])
                        f[j]=len;
                else    break;
        }

        printf("%d\n",ans);
    }
}