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

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

推荐阅读