#include #include #include #include #include #include #include #include #include #include using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef __int64 ll; const ll Inf = (ll)(1e15); const int N = 1000 + 10; const int M = 50 + 5; struct node { ll addv, min; }; struct tnode { int pos; ll cos; tnode() { } tnode(int _pos, ll _cos) { pos = _pos; cos = _cos; } }; node seg[N << 2]; vector a[M]; int val[M][N][2]; ll d[M][N]; void Up(node& fa, node &ls, node& rs) { if (ls.min > rs.min) { fa.min = rs.min; } else { fa.min = ls.min; } } void Down(node& fa, node& ls, node& rs) { if (fa.addv != 0) { ls.min += fa.addv; rs.min += fa.addv; ls.addv += fa.addv; rs.addv += fa.addv; fa.addv = 0; } } void build(int i, int p, int l, int r, int rt) { seg[rt].addv = 0; if (l == r) { seg[rt].min = d[i][l] + abs(p - a[i][l].pos); } else { int mid = (l + r) >> 1; build(i, p, lson); build(i, p, rson); Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); } } void update(int L, int R, ll v, int l, int r, int rt) { if (L <= l && r <= R) { seg[rt].min += v; seg[rt].addv += v; } else { int mid = (l + r) >> 1; Down(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); if (L > mid) update(L, R, v, rson); else if (R <= mid) update(L, R, v, lson); else { update(L, mid, v, lson); update(mid + 1, R, v, rson); } Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); } } void update_pos(int i, int j, int from, int to, int l, int r, int rt) { if (l == r) { int p = a[i][j].pos; ll v = (ll)-abs(p - from) + abs(p - to); seg[rt].min += v; seg[rt].addv += v; } else { Down(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); int mid = (l + r) >> 1; if (j <= mid) update_pos(i, j, from, to, lson); else update_pos(i, j, from, to, rson); Up(seg[rt], seg[rt << 1], seg[rt << 1 | 1]); } } bool cc(const tnode& i, const tnode& j) { return i.pos < j.pos; } void work() { for (int i = 0; i < M; ++i) a[i].clear(); int m, n, x, st, p, idx, idy; scanf("%d%d%d", &n, &m, &st); for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j) scanf("%d", &val[i][j][0]); for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j) scanf("%d", &val[i][j][1]); a[0].push_back(tnode(st, 0)); for (int i = 1; i <= n; ++i) { for (int j = 0; j < m; ++j) a[i].push_back(tnode(val[i][j][0], val[i][j][1])); sort(a[i].begin(), a[i].end(), cc); } // dp for (int i = 0; i <= n; ++i) for (int j = 0; j < a[i].size(); ++j) d[i][j] = Inf; d[0][0] = 0; for (int i = 1; i <= n; ++i) { p = a[i][0].pos; build(i - 1, p, 0, a[i - 1].size() - 1, 1); d[i][0] = a[i][0].cos + seg[1].min; // idx = -1; while (idx + 1 < a[i - 1].size() && a[i - 1][idx + 1].pos < p) ++ idx; idy = a[i - 1].size(); while (idy - 1 >= 0 && a[i - 1][idy - 1].pos > p) -- idy; // for (int j = 1; j < a[i].size(); ++j) { while (idy < a[i - 1].size() && a[i - 1][idy].pos <= a[i][j].pos) ++ idy; if (idx >= 0) update(0, idx, a[i][j].pos - p, 0, a[i - 1].size() - 1, 1); if (idy < a[i - 1].size()) update(idy, a[i - 1].size() - 1, p - a[i][j].pos, 0, a[i - 1].size() - 1, 1); // for (int k = idx + 1; k < idy; ++k) update_pos(i - 1, k, p, a[i][j].pos, 0, a[i - 1].size() - 1, 1); // d[i][j] = a[i][j].cos + seg[1].min; p = a[i][j].pos; while (idx + 1 < a[i - 1].size() && a[i - 1][idx + 1].pos < p) ++ idx; } } ll ans = Inf; for (int i = 0; i < a[n].size(); ++i) ans = min(ans, d[n][i]); cout << ans << endl; } int main() { int cas; scanf("%d", &cas); while (cas -- > 0) work(); return 0; }
AOJ 0121 Seven Puzzle {廣度優先搜索}
BZOJ 2876 NOI2012 騎行川藏 二分+數學算法
C++混合編程之idlcpp教程Python篇(9)，idl
Highcharts£ºXÖá·Ö×é¶Ñµþͼ ÔÚ
LeetCode解題報告--Search for a Ran
【描述】適配器模式將某個對象的接口適配為另一個對象所期
