首页 > ACM题库 > HDU-杭电 > HDU 3530-Subsequence-动态规划-[解题报告]HOJ
2014
11-05

HDU 3530-Subsequence-动态规划-[解题报告]HOJ

Subsequence

问题描述 :

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

输入:

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

输出:

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

样例输入:

5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5

样例输出:

5
4

这么一个破题折腾了我两天,还能说神马。。。烂的不能再烂了。。。。

应该说我刚开始想的还是基本正确的,但“基本”是不能容忍的。。。就是记录两个单调队列,一个单调不递减,另一个单调不递增。记录从后往前数的最大值和最小值,枚举以i为最后一个元素的符合题目要求的序列。当两个队头的差大于k时,这说明需要调整,增大最小值或减小最大值,缩短区间。至于我犯得两个错误,在这里就不说明了。然后就是确定区间长度,代码很简单,所以略掉,附代码:

#include <iostream>

#define cl(a) memset(a,0,sizeof(a))
#define ss(a) scanf("%d",&a)
 
using namespace std;
 
struct node
{
    int v;
    int id;
};

const int N=1000100;
node a[N],b[N],c[N];

int main()
{
    int i,n,k,m,zmax,l1,r1,l2,r2,x;
    while (ss(n)!=EOF)
    {
        ss(m);ss(k);
        for (i=1;i<=n;i++) 
        {
            ss(a[i].v);
            a[i].id=i;
        }
        cl(b);cl(c);
        l1=0;r1=1;
        l2=0;r2=1;
        b[0].id=c[0].id=0;
        zmax=0;
        for (i=1;i<=n;i++)
        {
            while (l1<=r1&&b[r1].v<a[i].v) r1--;
            b[++r1]=a[i];
            while (l2<=r2&&c[r2].v>a[i].v) r2--;
            c[++r2]=a[i];
            while (l1<=r1&&l2<=r2&&b[l1].v-c[l2].v>k)
            {
                if (b[l1].id<c[l2].id) l1++;
                else l2++;
            }
            if (l1<=r1&&l2<=r2&&b[l1].v-c[l2].v>=m)
            {
                if (b[l1-1].id>c[l2-1].id) x=b[l1-1].id;
                else x=c[l2-1].id;
                zmax=max(zmax,i-x);
            }
        }
        if (zmax==1&&m>0) zmax=0;
        printf("%d\n",zmax);
    }
    return 0;
}

 

 

参考:http://blog.csdn.net/liverpippta/article/details/8067712