【JZOJ4031】【CF261D】Maxim and Increasing Subsequence（DP）

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≤105 $n\ast t\le {10}^5$
　　对于100%的数据， 1≤k≤10 $1\le k\le 10$， 1≤n,maxb≤105 $1\le n,maxb\le {10}^5$， 1≤t≤109 $1\le t\le {10}^9$， n∗maxb≤2∗107 $n\ast maxb\le 2\ast {10}^7$

Solution

　　这道题我刚看还以为是什么高级的东西，比如说把它转化为矩阵乱乘一下，没想到就是个暴力……
　　首先，设b数组中互不相同的数的个数为cnt，则若t≥cnt，则答案定为cnt，直接continue。原因很显然。（但我比赛时竟然没想到！！！）
　　那么我们就发现，真正有用的t≤min(n,maxb)，所以可以直接模拟出a数组，而其长度≤ 2∗107 $2\ast {10}^7$。那样的话，直接对它求最长上升子序列即可。
　　我们可以使用朴素的二分优化，这样时间复杂度即为 O(k∗n∗t∗log(cnt)) $O(k\ast n\ast t\ast log(cnt))$。虽然n*t最大为 2∗107 $2\ast {10}^7$，再乘个k，已满 2∗108 $2\ast {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∗maxn) $O(k\ast n\ast t\ast maxn)$的，但是实际上我们对于同一len，它最多只会把整个f数组的值变为len，而f数组也就maxb的大小；而总共有至多cnt个不同的len。所以：
　　时间复杂度： O(k∗cnt∗maxb) $O(k\ast cnt\ast maxb)$。

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);
    }
}