[LgP1373] 小a和uim之大逃离

OI 题解 DP

算法：矩形DP

首先很自然的写出状态：f[i][j]表示(i, j)点处的方案数，但是，这样无法转移，首先，我们不知道这个点上是谁，所以改进为f[i][j][2]，第三维表示是a还是uim。但是这样还不够，我们依旧是无法转移，注意到如果把a和uim看作一个人装，一个人倒，那就是相当于要求差值模k+1为0，所以改进为f[i][j][k][2]，k表示差值。

为了避免讨论，我们将a[i][j]奇偶染色，这样，就保证了每一步都是一加一减。

由于起点不定，每个点都要初始化为1。

代码

inline int mod(int n, int md) { return (n % md + md) % md; }
int main() {
    scanf("%d%d%d", &n, &m, &k); 
    ++k; // 方便做
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
            if ((i + j) & 1) a[i][j] *= -1; // 奇偶染色
            a[i][j] = mod(a[i][j], k);
            f[i][j][a[i][j]][0] = 1;
            for (int res = 0, y; res < k; ++res) {
                y = mod(res-a[i][j], k);
                f[i][j][res][0] = ((f[i][j-1][y][1] + f[i-1][j][y][1]) % MOD 
                                  + f[i][j][res][0]) % MOD;
                f[i][j][res][1] = ((f[i][j-1][y][0] + f[i-1][j][y][0]) % MOD 
                                  + f[i][j][res][1]) % MOD;
            }
            ans = (ans + f[i][j][0][1]) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}