BZOJ 2669 - [cqoi2012]局部极小值

Published on 2016-06-13

题目地址

描述

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

分析

画图可得,局部极小值最多只有 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(is))×dp[i][s]dp[i+1][s]({num}_s - (i - \vert s\vert)) \times dp[i][s] \rightarrow dp[i + 1][s]

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

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

实际上是:只满足 ss 的矩阵 = 至少满足 ss 的矩阵 - 至少满足 t,stt, s \subset t 的矩阵的并集。
所以我们 DFS 一下增加局部极小值的位置即可,因为可以剪枝且局部极小值的位置最多只有 88 个,所以可以跑的飞起。
复杂度 O(288nmc)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;
}