题解：P7532 [USACO21OPEN] Balanced Subsets P

· · 题解

[USACO21OPEN] Balanced Subsets P

如果有蒟蒻想出状态但不会转移的请看这篇题解，就比如我

首先解析一下题目中“平衡”条件，就是实心凸多边形的充要条件，因为如果是凹的，一定会有一行/一列不连续。

求平衡连通块个数，显然是计数 DP。

那么从上到下扫一遍这个四边形，那么左、右端点一定是先扩张后收缩的，于是得到状态设计:

方便起见，我们把 $p$、$q$ 这两维称为“变化趋势”。 ## SubTask $n \le 50$ 的情况直接转移状态即可。 可以看看我的代码和图理解一下。 ![图1](https://cdn.luogu.com.cn/upload/image_hosting/a8p0xo8x.png) 时间复杂度 $O(n^5) 
#define int long long int
namespace SubTask {
/* O(n^5): 照状态直接转移即可，能拿到50pts高分
 */
void solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            ss[j] = ss[j - 1] + (s[i][j] == 'G');
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) { // 枚举这一个区间 [l, r]
                if (ss[r] - ss[l - 1] != r - l + 1)
                    continue;  // 没有填满色
                f[i][l][r][0][0] = 1; // 这个代表现在第 i 行的 [l, r] 是整个图形的顶部
                for (int x = 1; x <= n; x++)
                    for (int y = x; y <= n; y++) {  // 枚举上一个区间 [x, y]
                        // 注意到变化趋势：0可以转到1，但是1不可以转到0，如果是l/r不变那么认为l/r的变化趋势也不变

                        // l, r都扩张，变化趋势不变
                        if (l <= x && y <= r)
                            add(f[i][l][r][0][0], f[i - 1][x][y][0][0]);
                        // l一定保证扩张，分讨r是收缩/不变的两种情况
                        if (l <= x && x <= r && r < y)
                            add(f[i][l][r][0][1], f[i - 1][x][y][0][0]);
                        if (l <= x && x <= r && r <= y)
                            add(f[i][l][r][0][1], f[i - 1][x][y][0][1]);

                        // r一定保证扩张，分讨l是收缩/不变的两种情况
                        if (x < l && l <= y && y <= r)
                            add(f[i][l][r][1][0], f[i - 1][x][y][0][0]);
                        if (x <= l && l <= y && y <= r)
                            add(f[i][l][r][1][0], f[i - 1][x][y][1][0]);

                        // 分讨l是收缩/不变及r是收缩/不变的四种情况
                        if (x <= l && y >= r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][1][1]);
                        if (x < l && y >= r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][0][1]);
                        if (x <= l && y > r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][1][0]);
                        if (x < l && y > r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][0][0]);
                    }
                for (int c = 0; c < 4; c++)
                    add(ans, f[i][l][r][c >> 1][c & 1]);
            }
        }
    }
    printf("%lld\n", ans);
}
};

FullSolution

可以看出我们转移状态的时候用了 $x$ 和 $y$ 帮助转移，但这样也大大增加了我们的时间复杂度。 考虑去掉 $x$ 和 $y$ 这两层循环，把情况列出来试一试： ![图2](https://cdn.luogu.com.cn/upload/image_hosting/n969f4ki.png) 可以发现对于每种情况的 $x$ 和 $y$ ，它们分别都在一个连续区间内 于是把每一种情况用前缀和优化一下即可 时间复杂度 $O(n^3) 
#include <bits/stdc++.h>

#define int long long int

using namespace std;

const int N = 1.5e2 + 10, mod = 1e9 + 7;
int n;
char s[N][N];
int f[N][N][N][2][2]; // 见状态设计
int ss[N];

void add(int &x, int ad) { x = (x + (ad % mod + mod)) % mod; }

namespace SubTask {
/** O(n^5): 照状态直接转移即可，能拿到50pts高分
 */
void solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            ss[j] = ss[j - 1] + (s[i][j] == 'G');
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) { // 枚举这一个区间 [l, r]
                if (ss[r] - ss[l - 1] != r - l + 1)
                    continue;  // 没有填满色
                f[i][l][r][0][0] = 1; // 只有一层[l,r]的情况也要算在内
                for (int x = 1; x <= n; x++)
                    for (int y = x; y <= n; y++) {  // 枚举上一个区间[x, y]
                        // 注意到变化趋势：0可以转到1，但是1不可以转到0，如果是l/r不变那么认为l/r的变化趋势也不变

                        // l, r都扩张，变化趋势不变
                        if (l <= x && y <= r)
                            add(f[i][l][r][0][0], f[i - 1][x][y][0][0]);
                        // l一定保证扩张，分讨r是收缩/不变的两种情况
                        if (l <= x && x <= r && r < y)
                            add(f[i][l][r][0][1], f[i - 1][x][y][0][0]);
                        if (l <= x && x <= r && r <= y)
                            add(f[i][l][r][0][1], f[i - 1][x][y][0][1]);

                        // r一定保证扩张，分讨l是收缩/不变的两种情况
                        if (x < l && l <= y && y <= r)
                            add(f[i][l][r][1][0], f[i - 1][x][y][0][0]);
                        if (x <= l && l <= y && y <= r)
                            add(f[i][l][r][1][0], f[i - 1][x][y][1][0]);

                        // 分讨l是收缩/不变及r是收缩/不变的四种情况
                        if (x <= l && y >= r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][1][1]);
                        if (x < l && y >= r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][0][1]);
                        if (x <= l && y > r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][1][0]);
                        if (x < l && y > r)
                            add(f[i][l][r][1][1], f[i - 1][x][y][0][0]);
                    }
                for (int c = 0; c < 4; c++)
                    add(ans, f[i][l][r][c >> 1][c & 1]);
            }
        }
    }
    printf("%lld\n", ans);
}
};

namespace FullSolution {
/** O(n^3): 对于O(n^5)的算法，考虑优化
 *  发现每次f[i][...]转移加上的就是一个f[i-1][...]的子矩阵和
 *  所以去掉枚举x和y的两层，改为加上上一维对应f的子矩阵和
 */
int sf[N][N][2][2]; // f的前缀和 (滚掉[i]项)
void init_sf(int i) { // 处理f[i][...]的前缀和数组sf
    memset(sf, 0, sizeof(sf));
    for (int c = 0; c < 4; c++)
        for (int l = 1; l <= n; l++)
            for (int r = 1; r <= n; r++) {
                int p = c >> 1, q = c & 1;
                add(sf[l][r][p][q], sf[l - 1][r][p][q] + sf[l][r - 1][p][q] - sf[l - 1][r - 1][p][q] + f[i][l][r][p][q]);
            }
}
int getsum(int l1, int r1, int l2, int r2, int p, int q) { // 求子矩阵和
    int res = 0;
    l1--, l2--;
    add(res, sf[r1][r2][p][q] - sf[l1][r2][p][q] - sf[r1][l2][p][q] + sf[l1][l2][p][q]);
    return res;
}
void solve() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            ss[j] = ss[j - 1] + (s[i][j] == 'G');
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) { // 枚举这一个区间[l, r]
                if (ss[r] - ss[l - 1] != r - l + 1)
                    continue;  // 没有填满色
                add(f[i][l][r][0][0], 1 + getsum(l, r, l, r, 0, 0));
                add(f[i][l][r][0][1], getsum(l, r, r + 1, n, 0, 0)
                                    + getsum(l, r, r, n, 0, 1));
                add(f[i][l][r][1][0], getsum(1, l - 1, l, r, 0, 0)
                                    + getsum(1, l, l, r, 1, 0));
                add(f[i][l][r][1][1], getsum(1, l, r, n, 1, 1)
                                    + getsum(1, l - 1, r + 1, n, 0, 0)
                                    + getsum(1, l - 1, r, n, 0, 1)
                                    + getsum(1, l, r + 1, n, 1, 0));
                // 每一个getsum()都对应之前的一个分讨
                for (int c = 0; c < 4; c++)
                    add(ans, f[i][l][r][c >> 1][c & 1]);
            }
        }
        init_sf(i); // 更新一下f的前缀和
    }
    printf("%lld\n", ans);
}
};

main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);
    // SubTask::solve(); // 这里是O(n^5)的做法
    FullSolution::solve(); // 这是正解
    return 0;
}