UVa1408/LA4018 Flight Control

题目链接

  本题是2007年icpc亚洲区域赛成都赛区的F题

题意

  有一个N行M列的数组(1 ≤ N ≤ 50, 1 ≤ M ≤ 9)记录机场各个航班的飞行传感数据，其每个元素都是整数。如果某元素小于等于0，则其一定不是航班的飞行数据。如果某个元素大于0，则其可能是一个航班的飞行数据，也可能和所在行（或列）连续严格递增（或严格递减）的子序列一起构成一个航班的飞行数据。不同航班的传感数据不能重叠，求数组最少代表的航班数。

分析

  首先想到利用轮廓线动态规划处理覆盖问题的思路来求解，状态是4进制M位：每一位代表所在航班往上、下、左、右飞行。那么状态转移一共$4^M\ast M\ast N$次，最高达到$10^8$（117964800），这种原始做法会超过3s限时。

  对取值为左、右的状态位，可以发现仅仅在其为状态的末尾时才有可能影响当前的状态转移决策，末尾之前的那些状态位取值为左、右时无法影响当前的状态转移决策。因此，可以将状态定义成3进制（上、下、水平）再加上末尾是否为左右即可。这时状态转移一共$2\ast 3^M\ast M\ast N$次，最高达到$10^7$（17714700），3s内应该能过，写出此版本的代码验证发现大约运行2s：

#include <iostream>
#include <cstring>
using namespace std;

#define M 9
#define N 50
#define T 39366
int a[N][M], d[2][T], p[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683}, m, n, kase = 0;

void solve() {
    memset(d[0], 0, sizeof(d[0]));
    int c = 0, t = p[m]<<1, r = p[max(m-1, 0)], ans = m*n;
    for (int i=0; i<n; ++i) for (int j=0; j<m; ++j, c^=1) {
        int v, f = i ? a[i-1][j] : 0, l = j ? a[i][j-1] : 0;
        cin >> v; a[i][j] = v = max(v, 0); memset(d[c^1], 1, sizeof(d[0]));
        for (int k=0; k<t; ++k) {
            int h = (k>>1)/r, s = (k>>1)%3, e = (k>>1)%r, b = k&1;
            int &w = d[c^1][6*e], &x = d[c^1][6*e+1], &y = d[c^1][6*e+2], &z = d[c^1][6*e+4];
            w = min(w, d[c][k] + (v && (!l || s || l>=v || b)));
            x = min(x, d[c][k] + (v && (!l || s || l<=v || !b)));
            y = min(y, d[c][k] + (v && (!f || h!=1 || f>=v)));
            z = min(z, d[c][k] + (v && (!f || h!=2 || f<=v)));
        }
    }
    for (int i=0; i<t; ++i) ans = min(ans, d[c][i]);
    cout << "Case " << ++kase << ": " << ans << endl;
}

int main() {
    while (cin >> n >> m && (m || n)) solve();
    return 0;
}

  更进一步，由于利用行内连续3个元素（或者列内连续3个元素）可以判定能否水平（或者竖直）飞行以及飞行方向，那么状态可以用未定（代表当前位置为新航班）、水平、竖直这样的3进制来表示。状态转移一共$3^M\ast M\ast N$次，时间又缩短一半，并且可以利用备忘录dp来进一步优化时间。这种方法要注意一点：如果正上方位置取值是未定，而右上取值是水平，则当前位置决策时不能取到竖直。

AC 代码

#include <iostream>
#include <cstring>
using namespace std;

#define M 9
#define N 50
#define T 19683
int a[N][M], d[N][M][T], p[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, T}, m, n, kase = 0;

bool check(int a, int b, int c) {
    if (!a || !b || !c || a==b || b==c) return false;
    return a < b ? b < c : b > c;
}

int dp(int i, int j, int s) {
    if (i == n) return 0;
    if (j == m) return dp(i+1, 0, s);
    if (d[i][j][s] >= 0) return d[i][j][s];
    int &r = d[i][j][s], t = i ? a[i-1][j] : 0, l = j ? a[i][j-1] : 0, h = s / p[m-1], b = s % 3, c = a[i][j];
    r = dp(i, j+1, s % p[m-1] * 3) + (c != 0);
    if (c && l && ((!b && c != l) || (b==1 && check(a[i][j-2], l, c))))
        r = min(r, dp(i, j+1, s % p[m-1] * 3 + 1));
    if (c && t && ((!h && c != t && (j+1<m ? s/p[m-2]%3 : 0) != 1) || (h==2 && check(a[i-2][j], t, c))))
        r = min(r, dp(i, j+1, s % p[m-1] * 3 + 2));
    return r;
}

void solve() {
    memset(d, -1, sizeof(d));
    for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) cin >> a[i][j], a[i][j] = max(a[i][j], 0);
    cout << "Case " << ++kase << ": " << dp(0, 0, 0) << endl;
}

int main() {
    while (cin >> n >> m && (m || n)) solve();
    return 0;
}