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

直接用栈做辅助记录每条线段端点下去之后转移到的线段下标 然后做动态规划应该没错的吧

Posted by alpc12 at 2007-05-30 14:29:53 on Problem 2374
//不明白怎么WA了
#include <string.h>
#include <stdio.h>

#define abs(a) ((a) > 0 ? (a) : -(a))

const int N = 50010;
int n, s;
int a[N], b[N], l[N], r[N];
int stack[N];
int dp[N][2];

int main() {
	scanf("%d %d", &n, &s);
	int i, top;
	for(i = n-1; i>=0; i--) scanf("%d %d", &a[i], &b[i]);
	memset(l, -1, n * sizeof(int));
	memset(r, -1, n * sizeof(int));
	for(stack[0] = 0, top = 0, i = 0; i < n; ++i) {
		if(b[i] >= b[stack[top]]) {
			r[stack[top]] = i;
			stack[++top] = i;
		}
	}
	int fr = stack[top];
	top = 0, i = 0;
	stack[0] = 0;
	while(i < n) {
		if(a[i] <= a[stack[top]]) {
			l[stack[top]] = i;
			stack[++top] = i;
		}
		++i;
	}
	int fl = stack[top];

	memset(dp, -1, sizeof(dp));
	
	dp[0][0] = abs(s-a[0]);
	dp[0][1] = abs(s-b[0]); 
	for(i = 0; i < n; ++i) {
		if(l[i] != -1) { 
			if(dp[l[i]][0] == -1 || dp[i][0] + abs(a[i] - a[l[i]]) < dp[l[i]][0]) 
				dp[l[i]][0] = dp[i][0] + abs(a[i] - a[l[i]]);
			if(dp[l[i]][1] == -1 || dp[i][0] + abs(a[i] - b[l[i]]) < dp[l[i]][1]) 
				dp[l[i]][1] = dp[i][0] + abs(a[i] - b[l[i]]);
		}
		if(r[i] != -1) {
			if(dp[r[i]][0] == -1 || dp[r[i]][0] > dp[i][1] + abs(b[i] - a[r[i]]) )
				dp[r[i]][0] = dp[i][1] + abs(b[i] - a[r[i]]);
			if(dp[r[i]][1] == -1 || dp[r[i]][1] > dp[i][1] + abs(b[i] - b[r[i]]) )
				dp[r[i]][1] = dp[i][1] + abs(b[i] - b[r[i]]);
		}
	}

	int ans = 123456789;
	if(dp[fr][1] != -1 && dp[fr][1] + abs(b[fr]) < ans) ans = dp[fr][1] + abs(b[fr]);
	if(dp[fl][0] != -1 && dp[fl][0] + abs(a[fl]) < ans) ans = dp[fl][0] + abs(a[fl]);
	printf("%d\n", ans);

	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