小美的平衡矩阵_dp思路

小美的平衡矩阵

---

写在前面:
本博客只是一种解题思路的提供。

小美的平衡矩阵

题目描述：

小美拿到了一个n*n 的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i*i的完美矩形区域。你需要回答1<=i<=n的所有答案。

输入描述

第一行输入一个正整数n，代表矩阵大小。
接下来的n行，每行输入一个长度为n的01 串，用来表示矩阵。

输出描述

输出n行，第i行输出的I*I 完美矩形区域的数量。

示例 1

输入

4
1010
0101
1100
0011

输出

0
7
0
1

---

思路：

• 符合条件的矩阵的边一定是偶数，只有偶数才能保证 0和1的数量相等

• 确定一个矩阵只需要确定这个矩阵的四个顶点中的一个和边长m,这里选择右下角的顶点

• $arr[i][k]$ 记录了原始输入的$n\ast n$的矩阵

• $dp[m][i][k]$ 的含义是 $当边长为m时,右下角为arr[i][k]时的矩阵内数字和$

• 当矩阵内和为矩阵元素个数一半时，他是平衡矩阵。也就是说 当$\frac{m^2}{2}==dp[m][i][k]时$ ，这个矩阵是平衡矩阵

这里放一个$dp[i][k]$的版本，此时$dp[i][k]$的含义为：以$arr[1][1]$为左上元素，$arr[i][k]$为右下角元素的这个框内的所有元素和，此时的平衡矩阵的个数并不在dp中保存，而是作为一个临时变量存储（这一点切记）。

#include<iostream>
#include<vector>
#include<string>
using namespace std;int main(){int N,n,i=1,k;// N用于控制输入,n用于控制输出,i和k用于访问数组的元素cin>>N;string s;// 用于记录输入的01串n = N;vector<vector<int>> arr(N+1,vector<int>(N+1));vector<vector<int>> dp(N+1,vector<int>(N+1));while(N--){k = 1;while(k<=n){cin>>s;for(char ch:s){// 遍历01串中的每个字符,将其数字放入arr中arr[i][k++] = ch-'0';}++i;}}// 计算dp数组for(i = 1;i<=n;++i){for(k = 1;k<=n;++k){dp[i][k] = dp[i-1][k]+dp[i][k-1]-dp[i-1][k-1]+arr[i][k];            }}for(int m = 1;m<=n;++m){// 矩阵边长为1开始遍历,直到边长为nint ans = 0;if(m%2==0){// 只有边长为偶数的矩阵内才有可能使得 0和1的数目相等,保证可能存在平衡矩阵for(i = 1;i<=n;++i){for(k = 1;k<=n;++k){if(i>=m&&k>=m){unsigned long long num = dp[i][k]-dp[i-m][k]-dp[i][k-m]+dp[i-m][k-m];if(num==m*m/2)ans++;}}}}cout<<ans<<endl;}return 0;
}

---

有什么问题欢迎来讨论。

---

最开始思路：

$dp[r][q][i][k]$ 保存 以$arr[r][q]$为左上角 $arr[i][k]$ 为右下角的框内的元素和，发现dp的初始化和计算都比较麻烦，而且也计算了很多不符合条件的框（非正方形框）

稍微改进

$dp[m][i][k]$ 保存 边长为$m$时，框的右下角为元素 $arr[i][k]$时的这个框内的所有元素和，刨除了非正方形的框，

最后:

$dp[i][k]$ ,也就是代码版本

注意：本程序仅由简单测试，主要是提供思路。