CF 253D(矩阵-4角相等且矩阵权值有上限的矩阵数）

Posted on by
内容目录
D. 4a矩阵
time limit per test

2 seconds

memory limit per test

256 megabytes

input

input.txt

output

output.txt

有一个 n × m 的矩阵, 行 1 到 n,
列1 to m.

4a矩阵定义:

  • 矩阵内最多有 k 个 "a" ;
  • 4个角相等，长宽大于1.

请在给定矩阵中数出有几个子矩阵是4a矩阵.

Input

第一行3个整数n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).

接下来为矩阵.

Output

一个整数，表示4a矩阵数.

Sample test(s)
input
3 4 4
aabb
baab
baab
output
2
input
4 5 1
ababa
ccaca
ccacb
cbabc
output
1
Note

第一个样例的解 (2, 2) (3, 3),

(2, 1) (3, 4).

这题是状态压缩问题。

用s[i][j]=∑a[1][j]+a[2][j]+..+a[i][j]

那么我们只需要枚举3个量

行的上下，还有列的

显然r列的关系可以由r-1的关系推出。



#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (400+10)
#define MAXM (400+10)
int n,m,k;
char a[MAXN][MAXM];
int s[MAXN][MAXM];  //表示s[i][j]=a[1][j]+a[2][j]+..a[i][j]
int c[1<<8];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);


	memset(s,0,sizeof(s));
	scanf("%d%d%dn",&n,&m,&k);
	for (int i=1;i<=n;i++)
	{
		gets(a[i]+1);
		for (int j=1;j<=m;j++)
		{
			s[i][j]=s[i-1][j]+(a[i][j]=='a');
		}
	}
	long long ans=0;
	/*
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			cout<<s[i][j]<<' ';
		cout<<endl;
	}
	*/
	;
	for (int i=1;i<n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			int l=1,tot=0;
			memset(c,0,sizeof(c));
			for (int r=1;r<=m;r++)
			{
				tot+=s[j][r]-s[i-1][r];
				while (tot>k)
				{
					tot-=s[j][l]-s[i-1][l];
					c[a[i][l]]-=(a[i][l]==a[j][l]);
					l++;
				}
				if (l<r&&a[i][r]==a[j][r]) ans+=c[a[i][r]];
				if (a[i][r]==a[j][r]) c[a[i][r]]++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}