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