hdu 5064 满足b2−b1≤b3−b2... 的最长子序列

http://acm.hdu.edu.cn/showproblem.php?pid=5064

要找出一个数组中满足b2−b1≤b3−b2≤⋯≤bt−bt−1 的最大的t

直接引题解：

1003 Find Sequence

首先考虑解的结构一定是C1,C1,…,C1,C2,C3,…,Cm这种形式，其中满足C1<C2<C3<…<Cm

所以对a1,a2,a3,…,an去重后从小到大排序得到c1,c2,c3,…,cx其中x是sqrt(M)级别的，用DP[i][j]表示以ci和cj结尾的满足条件的最长序列

首先初值化 DP[i][i]=count(ci) 即ci在原序列中的个数。

而dp[i][j]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj−ci)+1

这样的复杂度是 O(x^3),在题中x最大为1000级别所以会超时，要使用下面优化

因为 dp[i][j]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj−ci)+1

dp[i][j+1]=max(dp[k][i] 其中k≤i还满足ci−ck≤cj+1−ci)+1

注意到cj+1>cj 所以满足ci−ck≤cj−ci的dp[k][i]必然满足ci−ck≤cj+1−ci因而不必重复计算

即最后复杂度可以为O(x^2).

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

int n,M;

const double pi = acos ( -1.0 ) ;

const LL modo = 1000000007;

int cnt[4200005],dp[2005][2005],c[2005];

void work()

{

    int x;

    clr0(cnt);

    for(int i = 0;i < n;++i){

        RD(x);

        cnt[x]++;

    }

    int m = 0;

    for(int i = 1;i <= M;++i)

        if(cnt[i]){

            c[m++] = i;

        }

    clr0(dp);

    for(int i = 0;i < m;++i){

        dp[i][i] = cnt[c[i]];

    }

    for(int i = 0;i < m;++i){

        int k = i,mx = dp[i][i];

        for(int j = i+1;j < m;++j){

            for(;k >= 0;--k){

                if(c[i] - c[k] <= c[j] - c[i]){

                    mx = max(mx,dp[k][i] + 1);

                }

                else    break;

            }

            dp[i][j] = mx;

        }

    }

    int ans = 0;

    for(int i = 0;i < m;++i)

        for(int j = i;j < m;++j)

            ans = max(ans,dp[i][j]);

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

    return;

}

int main () {

    int T;

    RD(T);

    while(T--){

        RD2(n,M);

        work();

    }

    return 0 ;

}