BZOJ 1126 - [POI2008]Uci | Sengxian's Blog

BZOJ 1126 - [POI2008]Uci

#动态规划

Published on 2016-09-28

描述

给一个 $n\times m(n,m\le 100)$ 的地图，计算从 $(n,1)$ 到第 $x$ 列的第 $y$ 行的路径条数 $\bmod k(k \le {10}^9)$ ，走过的点不能再走，转弯只能向右转。

分析

这个题目棘手的地方就在于，转弯只能向右转，这个限制是非常有意思的，我们怎么处理呢？观察走的路径，发现走的路径只能绕圈圈，如果从左下角走到 $(y, x)$ ，圈圈是越绕越小的，如果从 $(y, x)$ 走到左下角，圈圈是越绕越大的，我们考虑从 $(y, x)$ 走到左下角的路径条数。

设 $f[x_1][y_1][x_2][y_2][k]$ 为从 $(y, x)$ 出发，走过的路径的上边界是 $x_1$ ，下边界是 $x_2$ ，左边界是 $y_1$ ，右边界是 $y_2$ ，当前在右上角(0)，右下角(1)，左下角(2)，左上角(3)，的路径条数。

这样做避免了走重复的点，因为我们这个矩形是越走越大，不可能转移到比当前状态小的矩形。
我们考虑下右上角的转移，分为拐弯和不拐弯两种情况，下面是不拐弯：

f[x_1][y_1][x_2][y_2][0] \leftarrow f[x_1 + 1][y_1][x_2][y_2][0]

拐弯的话：

f[x_1][y_1][x_2][y_2][0] \leftarrow f[x_1][y_1][x_2][y_2 - 1][1]

没有别的情况了，这两种涵盖了所有的情况，这也是动态规划转移的思想，仅仅只考虑e最后一步，这里就是考虑拐不拐弯。其他角上的转移容易得出，唯一麻烦的是设立初值，我的方法是将起点 $(y, x)$ 需要的状态设置为 1（哪怕这个状态不合格），这样比较方便。

时间复杂度： $O(n^4)$ ，滚动一下第一维，空间复杂度： $O(n^3)$ 。

总结：对于棘手的 DP，要搞清楚有什么特性，根据特性设立状态，本题中就是观察到路径是一圈一圈的，从而用矩形来表示状态。

代码

//  Created by Sengxian on 2016/09/27.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1126 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 100 + 3, MAX_M = MAX_N;
int n, m, modu, x, y;
int sum[2][MAX_N][MAX_N];
int dp[2][MAX_M][MAX_N][MAX_M][4];

#define mod(a) ((a) %= modu)

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    scanf("%d%d%d%d%d", &n, &m, &modu, &y, &x);
    for (int i = 1; i <= n; ++i) {
        static char str[MAX_M];
        scanf("%s", str + 1);
        for (int j = 1; j <= m; ++j) {
            sum[0][i][j] = sum[0][i - 1][j] + (str[j] == '+');
            sum[1][i][j] = sum[1][i][j - 1] + (str[j] == '+');
        }
    }
    int ans = 0;
    dp[1][y][x][y][0] = 1;
    dp[0][y][x][y - 1][1] = 1;
    dp[0][y][x - 1][y][2] = 1;
    dp[0][y + 1][x][y][3] = 1;
    for (int x1 = x, _i = 0; x1 >= 1; --x1, _i ^= 1) {
        if (x1 != x) memset(dp[_i], 0, sizeof dp[_i]);
        for (int y1 = y; y1 >= 1; --y1)
            for (int x2 = x; x2 <= n; ++x2)
                for (int y2 = y; y2 <= m; ++y2) {
                    if (sum[0][x2][y2] - sum[0][x1 - 1][y2] == x2 - x1 + 1) {
                        dp[_i][y1][x2][y2][0] = dp[_i][y1][x2][y2 - 1][1];
                        if (x1 < x2) mod(dp[_i][y1][x2][y2][0] += dp[!_i][y1][x2][y2][0]);
                    }
                    if (sum[1][x2][y2] - sum[1][x2][y1 - 1] == y2 - y1 + 1) {
                        dp[_i][y1][x2][y2][1] = dp[_i][y1][x2 - 1][y2][2];
                        if (y1 < y2) mod(dp[_i][y1][x2][y2][1] += dp[_i][y1][x2][y2 - 1][1]);
                    }
                    if (sum[0][x2][y1] - sum[0][x1 - 1][y1] == x2 - x1 + 1) {
                        dp[_i][y1][x2][y2][2] = dp[_i][y1 + 1][x2][y2][3];
                        if (x1 < x2) mod(dp[_i][y1][x2][y2][2] += dp[_i][y1][x2 - 1][y2][2]);
                    }
                    if (sum[1][x1][y2] - sum[1][x1][y1 - 1] == y2 - y1 + 1) {
                        dp[_i][y1][x2][y2][3] = dp[!_i][y1][x2][y2][0];
                        if (y1 < y2) mod(dp[_i][y1][x2][y2][3] += dp[_i][y1 + 1][x2][y2][3]);
                    }
                    if (x1 == x && y1 == y && x2 == x && y2 == y) {
                            dp[1][y][x][y][0] = 0;
    dp[0][y][x][y - 1][1] = 0;
    dp[0][y][x - 1][y][2] = 0;
    dp[0][y + 1][x][y][3] = 0;
                    }
                    if (y1 == 1 && x2 == n) mod(ans += dp[_i][y1][x2][y2][2]);
                }
    }
    printf("%d\n", ans);
    return 0;
}

BZOJ 1127 - [POI2008]KUP BZOJ 1129 - [POI2008]Per