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