ZOJ 2283 Challenge of Wisdom

题意

在 N×M 的坐标系中，当你处在点 (x, y) 时，你可以移动到 (x+1, y) 或 (x, y+1) 。在图中有 P 个藏宝点。 除上述移动方式外，你还有转移到任意点的技能，问最少用多少次该技能，使得你能够拿到所有宝藏。

分析

貌似又一次彰显了我的无知，这竟然是最长反链的模板题，但是每次这种题目我都是模拟的 虽然最后代码不谋而合。

我主要谈谈我模拟的想法。

为使得转移技能用得最少，能够直接移动到达就必须尽可能选择移动。故对上述 P 个藏宝点，以 y 坐标从小到大排序。保证在选择的两点 poti, potj(i < j & poti.x<potj.x) 时，两点必然可通过直接移动到达。因此之后只需处理 P 个点的横坐标即可。

假设现在总共有 P 次的转移技能（显然最多使用技能 P 次能到达所有藏宝点），每次均转移到点 (0, 0) ，记为 mxi=0 。当从左到右遍历排序后的 P 个点时，对 poti.x ，查找当前最小的 i 使得 mxi 小于等于 poti.x ，并将该点移动到 poti.x 。判断使用到的最大的 mxi 的 i ，即为最终的答案。

代码

#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; struct Node { int x, y; } pot[100010]; bool cmp(Node a, Node b) { if(a.y == b.y) return a.x < b.x; return a.y < b.y; } int mx[100010], cnt; int get(int x) { int l = 0, r = cnt + 1, mid, ans = cnt + 1; while(l <= r) { mid = (l+r)>>1; if(mx[mid] > x) l = mid + 1; else r = mid - 1, ans = mid; } return ans; } int main() { for(int n, m, p;scanf("%d %d %d",&n,&m,&p)!=EOF;) { if(p == 0) { printf("0\n"); continue; } cnt = 0; memset(mx, 0, sizeof(mx)); for(int i=0;i<p;i++) scanf("%d %d",&pot[i].x, &pot[i].y); sort(pot, pot+p, cmp); for(int i=0, pos;i<p;i++) { pos = get(pot[i].x); cnt = max(cnt, pos); mx[pos] = pot[i].x; } printf("%d\n", cnt+1); } }