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:还是写成O(L)比较好

Posted by QWEDSA at 2012-05-26 21:28:28 on Problem 2373
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:
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