http://www.spoj.com/OI/problems/HERMES/
Brief description:
。。给定一个 [-m,m]×[-m,m] 的 Grid，要求顺次访问其中 n 个点。（只要和这个点处在同一行或同一列就判定为访问到）
。。你从 (0, 0) 出发，只能竖直或水平移动。。最小化总路程。
Analysis:
朴素 DP： 90 分
// 设：
// fx[i][yy] 路过了前 i 个，当前坐标在 (x[i], yy) 的 xxx。。。
// fy[i][xx] 路过了前 i 个，当前坐标在 (xx, y[i]) 的 xxx。。。
//}/* .................................................................................................................................. */
const int N = int(2e4) + 9, C = 1009;
int fx[2][C*2], fy[2][C*2], x[N], y[N];
int n;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out2.txt", "w", stdout);
#endif
REP_1_C(i, RD(n)){
RDD(x[i], y[i]);
}
#define fxq fx[q]
#define fxp fx[p]
#define fyq fy[q]
#define fyp fy[p]
int p = 0, q = 1; REP(i, 2*C) fxp[i] = fyp[i] = abs(i - C);
REP_1(i, n){
swap(p, q); RST(fxp, fyp);
REP(yy, 2*C) fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));
REP(xx, 2*C) fyp[xx] = min(fyq[xx]+abs(y[i]-y[i-1]), fxq[y[i]+C] + abs(xx-C-x[i-1]));
}
int res = INF; REP(i, 2*C){
checkMin(res, min(fxp[i], fyp[i]));
}
OT(res);
}
复杂度 O(nc)。。。这个状态和转移相对直白。。容易想到。。。
。。。考虑进一步优化。。。
我们要 keep in mind 的只有一件事。。。
“ 就是 dp 是可以拿数据结构紧凑地表示的。 。。。”
类似的例子有：
HDU Problem – 4703
Codeforces Round #172 Editorial
fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));
但是我们仍然发现右边的部分还是十分棘手。。。
需要对一个线性函数函数取 min 。。。。
以退为进！
我们对状态进行 redesign 。。！！。。
// fx[i][yy] 路过了前 i 个，当前坐标在 (x[i], yy) 的 xxx。。。
改成。。。
// fx[i][yy] 路过了前 i 个，当前坐标在 (x[i], yy) 的 xxx。。。但不允许到 x[i] 之后从 yy 上滑动。。。。。
细心的朋友可能就要问了？这有什么用呢？。。。。。。
考察转移：
fx’ -> fx 。。。。
。。注意到我们不会在 x[i-1] 这条直线上走。。（因为等价于在 x[i] 上走。。。）
因此可以直接从 fxq[yy] 转移。。看起来还是。。。
fxp[yy] = fxq[yy]+abs(x[i]-x[i-1]);
fy’ -> fx
。。注意。。。。我们的落点一定是在 (x[i], y[i-1])。。。
（否则。。假设我们的落点是 (x[i], y)。。那么 y[i-1] -> y 的这段位移。。同样可以放在 x[i] 上走。。。）
所以这里就变成了
fx[y[i-1]] = min(fy'[xx] + |xx-x[i]| );
和之前的状态设计中。。对应的这则转移比较。。。
REP(yy, 2*C) fxp[yy] = min(fxq[yy]+abs(x[i]-x[i-1]), fyq[x[i]+C] + abs(yy-C-y[i-1]));
从影响的状态是 O(n) 转移是 O(1)。。
变成了影响的状态是 O(1)。。转移是 O(n)。。。
而新的状态已经十分容易维护了。。。、、、
fx[y[i-1]] = min(fy'[xx] + |xx-x[i]| );
将绝对值拆开。。
fx[y[i-1]] = min( x[i] + min(fy'[xx]-xx) | xx <= x[i], min(fy'[xx]+xx) - x[i] | xx >= x[i] );
线段树维护即可。。 = =
Beautiful !!!
External Link:
Github Gist – http://www.spoj.com/OI/problems/HERMES/
后面一题：
贪心显然是不对的。。考虑乱搞：
官方题解：
“
首先对横线和竖线的坐标分别做镜像翻转，使它们的坐标分别都是单调递增的，
并且相邻的横线和相邻的竖线的距离根原始坐标的距离保持一致。这可以在线性时间内完成，
并且不影响答案。然后按照顺序扫描所有直线，维护从原点出发的两条移动路径。
一条移动路径尽可能往左走，一条移动路径尽可能往右走，
但都保持最短路并且满足规定的直线到达顺序。这两条移动路径分别是上凸曲线和下凸曲线，
每扫描到反向不同的两条直线时就根据交叉点更新其中一条移动路径。
扫描到最后一条直线时就可以算出最短的移动路径长度了。
”
尼玛第一句话就看不懂。
