Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:谁提供个代码啊,无论什么语言的,本人用的是pascal

Posted by kingbird2011 at 2012-07-18 10:04:09 on Problem 2373
In Reply To:谁提供个代码啊,无论什么语言的,本人用的是pascal Posted by:qzer at 2011-08-24 20:26:47
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#include <string.h>
#include <stdlib.h>
#define INF 9999999
int dp[1000009];
int queue[1000006][2];
int head,tail;
typedef struct segs
{
    int a,b;
}SEG;
SEG cover[1006];
SEG stack[1006];
int top;
int cmp(const void *a, const void *b)
{
    return ((SEG *)a)->a - ((SEG *)b)->a;
}
int main()
{
    int i,j, k;
    int n,l,a,b,temp;
    int sindex = 0,flag;
    scanf("%d%d%d%d", &n, &l, &a, &b);
    for(i = 0; i < n; i++)
    {
        scanf("%d%d", &cover[i].a, &cover[i].b);

    }
    qsort(cover,n,sizeof(SEG),cmp);
    top = 0;
    i = 0;

    for(i = 0; i < n; i++)
    {
        if(i+1 < n && cover[i].b > cover[i+1].a)
        {
            cover[i+1].b = max(cover[i+1].b, cover[i].b);
            cover[i+1].a = cover[i].a;
            continue;
        }else{
                stack[top++] = cover[i];
        }
    }
    head = tail = 0;
    queue[tail][0] = dp[0];
    queue[tail++][1] = 0;
    memset(dp, 0x7f, sizeof(dp));
    dp[0] = 0;
    for(i = 2; i <= l; i+=2)
    {
        temp = -1; flag = 0;
        while(sindex < top && stack[sindex].a < i)
        {
            sindex++;
            flag = 1;
        }
        if(flag)sindex--;

        if(i-2*a >= 0)
        {
            j = i-2*a;
            while(tail > head && dp[j] <= queue[tail-1][0])tail--;
            queue[tail][0] = dp[j];
            queue[tail++][1] = j;
        }

        while(head < tail && queue[head][1] < i-2*b)head++;
        if(head < tail && (stack[sindex].b <= i || stack[sindex].a >= i) &&
           queue[head][1] >= i-2*b && queue[head][1] <= i-2*a
           )dp[i] = queue[head][0]+1;
    }
    if(dp[l] < INF)printf("%d\n", dp[l]);
    else printf("-1\n");
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator