| ||||||||||
| 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 | |||||||||
直接用栈做辅助记录每条线段端点下去之后转移到的线段下标 然后做动态规划应该没错的吧//不明白怎么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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator