原题链接：P7532
前言
这道题是今天 NOIP 模拟赛的 T1，赛时只有 5 分。
题意
简化一下题意，即在一个 \(n\times n\) 的方阵中，求出有多少个满足条件的连通块，使得：
-
同一行或列的两点中间没有空
-
连通块内全是草
可以发现，其实连通块就是一个凸多边形。
思路
很显然，这道题是一道计数 DP。
因为时凸多边形，所以它的边只有两种情况——扩张和缩小。于是我们可以设计出状态：
\(dp_{i,l,r,p,q}\) 表示选完第 \(i\) 行，第 \(i\) 行选 \(l\) 至 \(r\) 的区间里的格子，左右端点分别处于扩张或缩小的状态。
很容易想到一个 \(O(n^{5})\) 的暴力DP，先枚举 \(i,l,r\)，再枚举 \(x,y\) 来转移。但这样转移肯定会超时，于是考虑优化。
我们会发现，其实每次方程转移时用的数据都是 \(f\) 数组里的一个子区间，于是可以用前缀和进行优化，做到 \(O(1)\) 去转移，这样整个代码的时间复杂度就时 \(O(n^{3})\) 的了，可以通过本题。
写法
现在我们知道要用前缀和了，到底要怎么求呢？可以看到下面的 get 函数
int get(int i,int l,int r,int x,int y,int p,int q) {
return (f[i][r][y][p][q] - f[i][l - 1][y][p][q] - f[i][r][x - 1][p][q] + f[i][l - 1][x - 1][p][q]) % mod;
}
首先，求前缀和的过程就是二维前缀和板子，不多赘述。
主要讲传入函数的参数的意义：
-
\(i\) 表示正在求的那一行的上一行，用已知推未知。
-
\(l\) 和 \(r\) 表示第 \(i\) 行左端点可能在的区间。
-
\(x\) 和 \(y\) 表示第 \(i\) 行右端点可能在的区间。
-
\(p\) 和 \(q\) 表示第 \(i\) 行左右端点分别处于扩张或缩小的状态。
怎么用这个前缀和呢，看下面代码：
dp[i][l][r][0][0] = (get(i - 1,l,r,l,r,0,0) + 1) % mod;
dp[i][l][r][0][1] = (get(i - 1,l,r,r + 1,n,0,0) + get(i - 1,l,r,r,n,0,1)) % mod;
dp[i][l][r][1][0] = (get(i - 1,1,l - 1,l,r,0,0) + get(i - 1,1,l,l,r,1,0)) % mod;
dp[i][l][r][1][1] = (get(i - 1,1,l - 1,r + 1,n,0,0) + get(i - 1,1,l - 1,r,n,0,1)) % mod;
dp[i][l][r][1][1] = (get(i - 1,1,l,r + 1,n,1,0) + get(i - 1,1,l,r,n,1,1) + dp[i][l][r][1][1]) % mod;
这里加一减一的细节很多，需要注意。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
#define inf 0x3f3f3f3f
typedef pair <int,int> pii;
const int MAXN = 160;
const int mod = 1e9 + 7;
int n,dp[MAXN][MAXN][MAXN][2][2],f[MAXN][MAXN][MAXN][2][2],sum[MAXN],ans;
char c[MAXN];
int get(int i,int l,int r,int x,int y,int p,int q) {
return (f[i][r][y][p][q] - f[i][l - 1][y][p][q] - f[i][r][x - 1][p][q] + f[i][l - 1][x - 1][p][q]) % mod;
}
signed main()
{
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> (c + 1);
for(int j = 1;j <= n;j++) sum[j] = sum[j - 1] + (c[j] == 'G');
for(int l = n;l >= 1;l--)
for(int r = l;r <= n;r++) {
if(sum[r] - sum[l - 1] != r - l + 1) continue;
dp[i][l][r][0][0] = (get(i - 1,l,r,l,r,0,0) + 1) % mod;
dp[i][l][r][0][1] = (get(i - 1,l,r,r + 1,n,0,0) + get(i - 1,l,r,r,n,0,1)) % mod;
dp[i][l][r][1][0] = (get(i - 1,1,l - 1,l,r,0,0) + get(i - 1,1,l,l,r,1,0)) % mod;
dp[i][l][r][1][1] = (get(i - 1,1,l - 1,r + 1,n,0,0) + get(i - 1,1,l - 1,r,n,0,1)) % mod;
dp[i][l][r][1][1] = (get(i - 1,1,l,r + 1,n,1,0) + get(i - 1,1,l,r,n,1,1) + dp[i][l][r][1][1]) % mod;
for(int p = 0;p < 2;p++) for(int q = 0;q < 2;q++) ans = (ans + dp[i][l][r][p][q]) % mod;
}
for(int j = 1;j <= n;j++)
for(int k = 1;k <= n;k++)
for(int p = 0;p <= 1;p++)
for(int q = 0;q <= 1;q++)
f[i][j][k][p][q] = (((f[i][j - 1][k][p][q] + f[i][j][k - 1][p][q]) % mod - f[i][j - 1][k - 1][p][q]) + dp[i][j][k][p][q]) % mod;
}
cout << (ans + mod) % mod;
return 0;
}