链接： Luogu-P2733
题意
在正方形的区域内，有一些点有标记，求出边长大于等于2的，内部没有标记的每种不同正方形个数。正方形可以重叠。
分析
- 不同正方形的个数？ 我们知道DP题目的常用方法是“看题说话”。我们可以根据题目信息直接定义状态吗？确定这个区域内的某一个正方形的两个量，分别是右下角（或者左上角等）的位置$(x,y)$，以及它的边长。但是，以两者中的任意一个定义状态，都不方便写出转移方程。 怎么办呢？
- 考虑将计数问题转化为最优问题。 计数问题和最优问题是动态规划研究的两类主要问题。其实，它们之间并不是没有关系的。 考虑与本题相关的一个最优问题： 以某个位置为右下角，最大的可能的正方形有多大？ 显然可以定义状态$f(i,j)$，表示以$(i,j)$为右下角的最大可能正方形的边长。 （这里借用下yangle61课件里面的几张图）
-
进行状态转移，要对解做出限制 当$(i,j)$处本身不是障碍时：
画出这个可能的最大正方形，把有标记的方块，即障碍块沿着这个正方形的边界移动，试着去寻找它的大小和$f(i-1,j)$,$f(i,j-1)$之间的联系。
通过画图可以发现，一定有 $f(i,j) \leq f(i-1,j) + 1$, $f(i,j) \leq f(i,j-1) + 1$。 这样就完全地限制了$f(i,j)$的取值吗？显然没有。如上图中2,4的情况，并没有被$f(i-1,j)$，$f(i,j-1)$严格地限制。
显然，$f(i,j)$还被$f(i-1,j-1)$所限制，即须有$f(i,j) \leq f(i-1,j-1) + 1$。 再画画图，发现，这样就完全地限制了$f(i,j)$的取值。
-
当$(i,j)$处本身是障碍时:显然$f(i,j)=0$
状态转移方程： \(f(i,j)=\begin{cases} \min \begin{cases} f(i-1,j)+1 & \text{ 如果 } i \geq 2 \\ f(i,j-1)+1 & \text{ 如果 } j \geq 2 \\ f(i-1,j-1)+1 & \text{ 如果 } i \geq 2 \text { 且 } j \geq 2 \end{cases} \\ 0 \text{ 如果 (i,j) 被挡住 } \end{cases}\)
-
回归题目 我们要做的最后一件事情，就是把最优问题转化回题目中的计数问题。 对于一个位置，我们已经知道了以它为右下角的正方形最大边长。同时，如果以$(i,j)$为右下角的最大正方形边长为$k$，那么边长为$k-1,k-2,…,2$的正方形均可行！ 于是我们有了这样的算法：如果全局最大的可行的正方形边长为$k$，那么一定可以统计出边长为$k$的正方形数目；然后把这个数目叠加到边长为$k-1$的正方形的数目上，如此往复。 为什么这样可行而不会重复呢？ 显然，当统计某个边长$l$的正方形时，由于我们算出的是每个位置的可行的最大正方形，该位置的边长小于$l$的正方形均没有统计，用如上的累加方法可以统计上这些正方形；如果某种边长小于$l$的正方形也是其所在位置的最大正方形，它就不会被重复统计。因此，这样可以不重不漏地统计出所有的正方形。
代码
注意：为何不需要判断$f(i,j)$是否越界呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <cctype>
#define min(x,y) (((x)>(y))?(y):(x))
#define max(x,y) (((x)<(y))?(y):(x))
using namespace std;
const int MAXN=250;
int N,Mx,f[MAXN+5][MAXN+5],T[10000010],Map[MAXN+5][MAXN+5];//True for obstacle
char readc(){
char c=getchar();
while(!isgraph(c)) c=getchar();
return c;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
Map[i][j]=(readc()=='0');
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(!Map[i][j]){
f[i][j]=min(
min(f[i-1][j],f[i][j-1]),
f[i-1][j-1]
)+1;
T[f[i][j]]++;
Mx=max(Mx,f[i][j]);
}
for(int i=Mx;i>=3;i--)
T[i-1]+=T[i];
for(int i=2;i<=Mx;i++)
if(T[i])
printf("%d %d\n",i,T[i]);
return 0;
}
