BZOJ 2669 - [cqoi2012]局部极小值

#DP #容斥原理
Published on 2016-06-13

题目地址

描述

有一个 n(1≤n≤4)n(1\le n\le 4) 行 m(1≤m≤7)m(1\le m\le 7) 列的整数矩阵，其中 11 到 nmnm 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。
给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

分析

画图可得，局部极小值最多只有 88 个，十分少，这启发我们状态压缩 DP。
而局部最小值比相邻的所有格子都小，那么可以利用这个性质，从小到大填数。
设 dp[i][s]dp[i][s] 为已填完数 [1,i][1, i]，已填局部最小值的情况为 ss，的方案数，dp[0][0]=1dp[0][0] = 1。

则考虑从已知的状态枚举下一个填数的位置，下一个填数的位置可以是未填过的某个局部最小值：

下一个填数的位置也可以是“某个格子”，“某个格子”不能是局部最小值，也不能是未填过的局部最小值周围的格子，我们可以预处理出 nums{num}_s 为已选的局部最小值为 ss 的情况下“某个格子”的数量。

(nums−(i−∣s∣))×dp[i][s]→dp[i+1][s]({num}_s - (i - \vert s\vert)) \times dp[i][s] \rightarrow dp[i + 1][s]

减去 (i−∣s∣))(i - \vert s\vert)) 的意思是减去已经填过的“某个格子”的数量。
最后 dp[nm][ALL]dp[nm][ALL] 就是保证给定位置是局部最小值的矩阵个数。

是不是就做完了呢？不是，我们求的是“保证给定位置是局部最小值的矩阵个数”，并不是“保证只有给定位置是局部最小值的矩阵个数”，也就是有可能别的位置是局部最小值。考虑容斥原理，设 ss 为题目所给局部最小值的位置集合，f(s)f(s) 为满足 ss 的矩阵集合，则容斥可得：

实际上是：只满足 ss 的矩阵 = 至少满足 ss 的矩阵 - 至少满足 t,s⊂tt, s \subset t 的矩阵的并集。
所以我们 DFS 一下增加局部极小值的位置即可，因为可以剪枝且局部极小值的位置最多只有 88 个，所以可以跑的飞起。
复杂度 O(28∗8∗n∗m∗c)O(2^8 * 8 * n * m * c)，cc 是总共容斥的项数。

没有做出来的原因：没有考虑到从小到大添加数字可以大大减小状态，没有考虑到需要容斥（什么也没想到）。
出题人想考什么：状态压缩 DP 的状态制定，容斥原理。
总结：DP 定状态要根据题目特性来定，而不是盲目的定。如果题目要求正好，而我们求的是至少，那么就可以考虑容斥了。

代码

//  Created by Sengxian on 6/13/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2669 容斥原理 + 状压 DP 
#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 * 10 + ch - '0', ch = getchar();
    return n;
}

const int maxn = 4 + 1, maxm = 7 + 1, modu = 12345678;
const int maxs = 8;
const char FLAG = 'X';
char str[maxn][maxm];
int n, m, cnt = 0, x[maxn * maxm], y[maxn * maxm];
int dp[maxn * maxm][1 << maxs], num[1 << maxs];

inline int check(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m;
}

int Dp() {
    cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (str[i][j] == FLAG) x[cnt] = i, y[cnt] = j, cnt++;

    for (int s = (1 << cnt) - 1; s >= 0; --s) {
        static bool block[maxn][maxm];
        memset(block, 0, sizeof block);
        for (int i = 0; i < cnt; ++i) if (!((s >> i) & 1)) {
            for (int dx = -1; dx <= 1; ++dx)
                for (int dy = -1; dy <= 1; ++dy) {
                    int _x = dx + x[i], _y = dy + y[i];
                    if (check(_x, _y)) block[_x][_y] = true;
                }
        }
        num[s] = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) if (str[i][j] != FLAG && !block[i][j])
                num[s]++;
    }

    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;

    for (int i = 0; i < n * m; ++i) {
        for (int s = (1 << cnt) - 1; s >= 0; --s) if (dp[i][s]) {
            //安放局部极小值
            for (int j = 0; j < cnt; ++j) if (!((s >> j) & 1))
                (dp[i + 1][s | (1 << j)] += dp[i][s]) %= modu;
            (dp[i + 1][s] += dp[i][s] * (num[s] - (i - __builtin_popcount(s))) % modu) %= modu;
        }
    }

    return dp[n * m][(1 << cnt) - 1];
}

int ans = 0;

void Dfs(int i, int j, int sign) {
    if (j == m) return Dfs(i + 1, 0, sign);
    if (i == n) {
        (ans += Dp() * sign) %= modu;
        return;
    }
    Dfs(i, j + 1, sign);
    for (int dx = -1; dx <= 1; ++dx)
        for (int dy = -1; dy <= 1; ++dy) {
            int _x = dx + i, _y = dy + j;
            if (check(_x, _y) && str[_x][_y] == FLAG) return;
        }
    str[i][j] = FLAG;
    Dfs(i, j + 1, -sign);
    str[i][j] = '.';
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n; ++i) {
        scanf("%s", str[i]);
        for (int j = 0; j < m; ++j) if (str[i][j] == FLAG) x[cnt] = i, y[cnt] = j, cnt++;
    }

    for (int i = 0; i < cnt; ++i) {
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy) if (abs(dx) + abs(dy)) {
                int _x = dx + x[i], _y = dy + y[i];
                if (check(_x, _y) && str[_x][_y] == FLAG) return puts("0"), 0;
            }
    }

    //容斥的计算，因为题目要求只能有给定的位置是局部最小值，而我们虽然能保证给定的位置是局部最小，却不能保证其余的地方不是局部最小值。
    Dfs(0, 0, 1);
    printf("%d\n", (ans + modu) % modu);
    return 0;
}
BZOJ 2142 - 礼物