自动搬运

查看原文

来自洛谷，原作者为

	Khan_ 已故（AFO五年老人了）

搬运于2025-08-24 21:40:57，当前版本为作者最后更新于2018-02-19 19:11:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

矩阵DP,PJ蒟蒻首次题解（老师讲了一遍还是没有听懂，后来想了好久的说）。

用的是老师讲的方法，f[i][j]表示以i,j为右下角所能扩展的最大矩阵大小由于f[i][j]是由f[i-1][j],f[i-1][j-1]和f[i][j-1]决定的，所以方程为f[i][j]=min(f[i-1][j],f[i-1][j-1]),f[i][j-1])
代码见下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX=300;
const int INF=0X3F3F3F3F;
int n;
char map[MAX][MAX];
int num[MAX*MAX];//用桶排进行存储，num[i]表示第i大的矩阵有num[i]个 
int f[MAX][MAX];//表示以map[i][j]为右下角的矩阵的最大值 
int main()
{
 cin>>n;
 for(int i=0;i<n;i++)
 cin>>map[i];
 /*---考虑边界情况---*/ 
 for(int i=0;i<n;i++)
 f[i][0]=(map[i][0]=='1');
 for(int j=0;j<n;j++)
 f[0][j]=(map[0][j]=='1');
 /*---全矩阵扫进行DP---*/
 for(int i=1;i<n;i++)
 	for(int j=1;j<n;j++)
 	if(map[i][j]=='1')//当前这个点不是障碍
 	{
 		f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
 		num[f[i][j]]++;
 	}
 /*---统计全部个数（实现方式有点像斐波那契数列）---*/
 for(int i=n;i>0;i--)
 num[i-1]+=num[i];
 /*---输出结束---*/
 for(int i=2;i<=n;i++)
 if(num[i])
 cout<<i<<' '<<num[i]<<endl;		 
}