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