Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:谁提供个代码啊,无论什么语言的,本人用的是pascalIn 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator