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

第一个 完完全全 自己推公式 单调队列优化出来的DP,,贴代码纪念!!!

Posted by 20107926LJW at 2012-07-22 21:39:14 on Problem 2373
//
//  代码可能比较冗余 , 莫拍砖,,学习中 --> _ --> 
//
#include <cstdio>	
#include <cstring>
#include <algorithm>
#define maxn 1000011
using namespace std;
typedef struct nn{
	int l ,r;
}node;
node crows[1001];

typedef struct QU{
	int id ,val;
}QUE;
QUE que[maxn >> 1];

bool cmp(const node a, const node b){
	return a.r < b.r;								//按照思想检查算法  此处应是按照 牛的右边界排序。。 贡献了几次wa
}
int dp[maxn] ;

int binsearch (int val,int l, int r){				//二分查找 单调队列
	int mid;
	while(l <= r){
		mid = (l + r) >> 1;
		if (que[mid].val >= val)					//队列数组是升序排列升序,查找第一个比他小的
			r = mid -1;
		else
			l = mid + 1;
	}
	return r;
}

int main(){
	int i ,j ,k ,a ,b ,l ,R ,r ,L ,n ,top ,rear ,index;
	QUE temp;
	while (~scanf("%d%d",&n ,&L)){
		scanf("%d%d",&a,&b);
		for (i = 0; i < n ;i ++)	scanf("%d%d",&crows[i].l,&crows[i].r);
		sort(crows ,crows + n , cmp);
		top = rear = 1;
		que[1].val = 99999999;
		que[1].id = 0;
		dp[0] = 0 ;
		for (i = 1; i < 2 * a; i ++) dp[i] = -1;							//
		for (i = 2 * a; i <= L ; i ++ ){
			if (i % 2  ) {
				dp[i] = -1 ;
				continue;
			}
			if (dp[i - 2 *a] != -1){
				index = binsearch(dp[i - 2 * a] ,top ,rear);	
				temp.id = i - 2 * a ;
				temp.val = dp[i - 2 * a];								   /// 初始化dp 数组
				rear = index + 1;
				que[rear] = temp ;
			}
			while (i - que[top].id > 2 * b && top <= rear) top++;
			if (que[top].val == 99999999 || top > rear) dp[i] = -1;
			else dp[i] = que[top].val + 1;
		}																	///
		for (i = 0 ;i < n ; i ++) {
			R =  ( crows[i].r % 2 == 1)? crows[i].r +1 : crows[i].r;
			l = crows[i].l;
			top = rear = 1;
			que[1].val = 99999999;
			que[1].id = 0;
			for ( j = l + 1 ; j < R ;j ++) 	dp[j] = -1 ;
			for ( j = R - 2 * b < 0 ? 0 :R - 2 * b; j < R - 2 * a; j ++ ) {
				if (dp[j] != -1){
				index = binsearch(dp[j] ,top ,rear);
				temp.id = j;
				temp.val = dp[j];
				rear = index + 1;
				que[rear] = temp ;
				}
			}
			int l1 = L ;                                 //
			if  (i != n -1 )							 //  此三行TLE 后反应过来 的优化
				l1 = min (l1 ,crows[ i+ 1].l);			 //
			for ( j = R ; j <= l1 ; j ++) {
				if (j % 2  ) {
					dp[j] = -1 ;
					continue;
				}
				if (dp[j - 2 *a] != -1){
					index = binsearch(dp[j - 2 * a] ,top ,rear);
					temp.id = j - 2 * a ;
					temp.val = dp[j - 2 * a];
					rear = index + 1;
					que[rear] = temp ;
				}
				while (j - que[top].id > 2 * b && top <= rear) top++;
				if (que[top].val == 99999999 || top > rear) dp[j] = -1;
				else dp[j] = que[top].val + 1;
			}
		}
		printf("%d\n",dp[L]);
	}
	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