| ||||||||||
| 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:还是写成O(L)比较好In Reply To:还是写成O(L)比较好 Posted by:20053565 at 2010-12-27 22:41:39 //谁能帮我找个错
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
typedef unsigned int UINT;
#define LMAX 1000000
#define COWMAX 1000
UINT dp[LMAX+1];
int ddqueue[LMAX];
int top = 0;
int bottom = 1;
int last = 0;
int ncow, Length;
int A, B;
struct cow
{
int S;
int E;
cow *next;
};
cow cowlist[COWMAX];
void prune(cow *a, cow *b)
{
cow *pnow = a, *pnext = a;
while(pnext < b)
{
if(pnext->S == pnow->S)
++pnext;
else
{
pnow->next = pnext;
pnow = pnext;
}
}
pnow->next = NULL;
}
void make2(cow* p)
{
do
{
if(p->S%2)
--p->S;
if(p->E%2)
++p->E;
p = p->next;
}while(p != NULL);
}
void cmerge(cow *p)
{
cow *pnext;
while((pnext = p->next) != NULL)
{
if(p->E > pnext->S)
{
p->E = max(p->E, pnext->E);
p->next = pnext->next;
}
else
p = pnext;
}
p->next = NULL;
}
int cmp(const void *a, const void *b)
{
const cow *p = (cow*)a;
const cow *q = (cow*)b;
if(p->S != q->S)
return p->S > q->S;
else
return p->E > q->E;
}
void dpmin(int pos)
{
if(pos <= 2*B)
{
int a = pos - 2*B;
int b = pos - 2*A;
a = max(a, 0);
b = max(b, 0);
int i;
UINT minnum = dp[a];
for(i = a; i <= b; ++i)
minnum = minnum<dp[i]?minnum:dp[i];
if(minnum != UINT_MAX)
++minnum;
dp[pos] = minnum;
}
else
{
int pos2A = pos - 2*A;
int pos2B = pos - 2*B;
for(last+=2; last <= pos2A; last+=2)
{
while(top >= bottom && dp[ddqueue[top]] > dp[last])
--top;
ddqueue[++top] = last;
while(top >= bottom && ddqueue[bottom] < pos2B)
++bottom;
}
last -= 2;
if(dp[ddqueue[bottom]] != UINT_MAX)
dp[pos] = dp[ddqueue[bottom]]+1;
else
dp[pos] = UINT_MAX;
}
}
void slove()
{
int i = 2;
cow *p = cowlist;
dp[0] = 0;
ddqueue[++top] = 0;
while(i <= Length)
{
if(p != NULL)
{
if(i > p->S)
{
i = p->E;
dpmin(i);
i += 2;
p = p->next;
continue;
}
}
dpmin(i);
i += 2;
}
}
int main()
{
scanf("%d%d%d%d", &ncow, &Length, &A, &B);
if(Length < 2*A || Length%2)
{
printf("-1\n");
return 0;
}
for(int i = 0; i < ncow; ++i)
scanf("%d%d", &cowlist[i].S, &cowlist[i].E);
memset(dp, UINT_MAX, sizeof(dp));
qsort(cowlist, ncow, sizeof(cow), cmp);
prune(cowlist, cowlist+ncow);
make2(cowlist);
cmerge(cowlist);
slove();
if(dp[Length] == UINT_MAX)
printf("-1\n");
else
printf("%d\n", dp[Length]);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator