Codeforces 704B - Ant Man

#图论 #动态规划 #好题
Published on 2016-08-11

题目地址

描述

有 n(2≤n≤5000)n(2\le n\le 5000) 个点，从左到右依次标号 。要求找一条从 的路径，经过每个点恰好一次且路径长度最小。
每个点有一个坐标 ，还有 4 个参数 ai,bi,ci,di(1≤ai,bi,ci,di≤109)a_i, b_i, c_i, d_i(1\le a_i, b_i, c_i, d_i\le {10}^9)，从 i→ji\rightarrow j 的代价是：

  • ∣xi−xj∣+ci+bj,j<i\vert x_i - x_j \vert + c_i + b_j, j < i
  • ∣xi−xj∣+di+aj,j>i\vert x_i - x_j \vert + d_i + a_j, j > i

分析

这题很像旅行商问题（Travelling salesman problem, TSP），事实上也可以规约到旅行商问题，是不是这个题就没有多项式时间复杂度的解法了呢？不同之处在于旅行商问题的权值是随机的，而这个题中的权值是有迹可循的，所以仍然存在多项式时间复杂度的解法。

观察边的权值的形式，发现只要知道了大小关系，那么权值就可以拆开来单独计算，所以我们可以进行从小到大的 DP。
考虑最优答案，它是一个起点为 ss，终点为 tt 的有向图。我们看前 ii 个节点的生成子图，它包含多个联通块，每个联通块都是一条链，只有 3 种链：

  1. 起点为 ss 的链（只能向最后加点）
  2. 不含 s,ts, t 的链（两边都可以加点）
  3. 终点为 tt 的链（只能从前面加点）

显然 1, 3 最多只有 1 条，2 不会超过 nn 条，设 dp[i][j][k][l]dp[i][j][k][l] 为考虑前 ii 个节点的生成子图，有 jj 条 1，kk 条 2，ll 条 3 时的最小答案。
我们刷表转移，考虑将 i+1i + 1 加入图，则 i+1i + 1 的作用要么是连接两条链，要么是在一条链的前或后，要么是单独形成链（其前驱后继的标号比他大），根据各种情况，可以拆开算代价。
注意 i+1=si + 1 = s 或 i+1=ti + 1 = t 的单独讨论，以及只有到最后才能连接 s,ts, t 链。

没有说的很详细的原因是情况比较多，但是都比较简单，代码有注释很容易看懂。其实是我懒

本题好在从小到大处理，可以让权值拆开计算，从而将多变的节点，转换为一条条链，而链的效果是一样的，所以可以大大减少状态。
总结：对于大量状态的 DP，需观察题目的特性，想办法分开算代价，这样才能减少状态，达到一个合理的复杂度。

代码

//  Created by Sengxian on 8/10/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 704B DP
# pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 5000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dp[2][2][maxn][2];
int x[maxn], a[maxn], b[maxn], c[maxn], d[maxn];
int n, s, t;

#define small_to_big_i(i) (d[i] - x[i])
#define small_to_big_j(j) (x[j] + a[j])
#define big_to_small_i(i) (x[i] + c[i])
#define big_to_small_j(j) (b[j] - x[j])

template <class T>
inline void tension(T &a, const T &b) {
    if (b < a) a = b;
}

int main() {
    n = ReadInt(), s = ReadInt(), t = ReadInt();
    for (int i = 1; i <= n; ++i) x[i] = ReadInt();
    for (int i = 1; i <= n; ++i) a[i] = ReadInt();
    for (int i = 1; i <= n; ++i) b[i] = ReadInt();
    for (int i = 1; i <= n; ++i) c[i] = ReadInt();
    for (int i = 1; i <= n; ++i) d[i] = ReadInt();
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
        register int _i = i & 1;
        memset(dp[!_i], 0x3f, sizeof dp[!_i]);
        for (int j = 0; j < 2; ++j) //s->xxx
            for (int k = 0; k < n; ++k)
                for (int l = 0; l < 2; ++l) if (dp[_i][j][k][l] < INF) {//xxx->t
                    if (i + 1 == s) {
                        if (k) tension(dp[!_i][1][k - 1][l], dp[_i][j][k][l] + big_to_small_i(i + 1)); //接在普通链前
                        tension(dp[!_i][1][k][l], dp[_i][j][k][l] + small_to_big_i(i + 1)); //自成一条链
                        if (i + 1 == n) tension(dp[!_i][0][k][0], dp[_i][j][k][l] + big_to_small_i(i + 1)); //s 接在 t 链上
                    } else if (i + 1 == t) {
                        if (k) tension(dp[!_i][j][k - 1][1], dp[_i][j][k][l] + small_to_big_j(i + 1)); //接在普通链后
                        tension(dp[!_i][j][k][1], dp[_i][j][k][l] + big_to_small_j(i + 1)); //自成一条链
                        if (i + 1 == n) tension(dp[!_i][0][k][0], dp[_i][j][k][l] + small_to_big_j(i + 1)); //t 接在 s 链上
                    } else {
                        if (k || j) tension(dp[!_i][j][k][l], dp[_i][j][k][l] + small_to_big_j(i + 1) + small_to_big_i(i + 1)); //接在链后
                        if (k || l) tension(dp[!_i][j][k][l], dp[_i][j][k][l] + big_to_small_i(i + 1) + big_to_small_j(i + 1)); //接在链前
                        if (k >= 2) tension(dp[!_i][j][k - 1][l], dp[_i][j][k][l] + small_to_big_j(i + 1) + big_to_small_i(i + 1)); //接在普通链中间
                        if (k && (j || l)) tension(dp[!_i][j][k - 1][l], dp[_i][j][k][l] + small_to_big_j(i + 1) + big_to_small_i(i + 1)); //接在 s 链以及普通链中间 或 接在 t 链以及普通链中间
                        if (i + 1 == n) tension(dp[!_i][0][k][0], dp[_i][j][k][l] + small_to_big_j(i + 1) + big_to_small_i(i + 1)); //接在 s 链与 t 链中间
                        tension(dp[!_i][j][k + 1][l], dp[_i][j][k][l] + small_to_big_i(i + 1) + big_to_small_j(i + 1)); //自成一条链
                    }
            }
    }
    printf("%lld\n", dp[n & 1][0][0][0]);
    return 0;
}
BZOJ 4407 - 于神之怒加强版