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

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(&quot;%d%d%d\n&quot;,&amp;n,&amp;m,&amp;k);
for (int i=1;i&lt;=n;i++)
{
    gets(a[i]+1);
    for (int j=1;j&lt;=m;j++)
    {
        s[i][j]=s[i-1][j]+(a[i][j]=='a');
    }       
}
long long ans=0;
/*
for (int i=1;i&lt;=n;i++)
{
    for (int j=1;j&lt;=m;j++)
        cout&lt;&lt;s[i][j]&lt;&lt;' ';
    cout&lt;&lt;endl;
}
*/
;   
for (int i=1;i&lt;n;i++)
{
    for (int j=i+1;j&lt;=n;j++)
    {
        int l=1,tot=0;
        memset(c,0,sizeof(c));
        for (int r=1;r&lt;=m;r++)
        {
            tot+=s[j][r]-s[i-1][r];
            while (tot&gt;k)
            {
                tot-=s[j][l]-s[i-1][l];
                c[a[i][l]]-=(a[i][l]==a[j][l]);
                l++;
            }   
            if (l&lt;r&amp;&amp;a[i][r]==a[j][r]) ans+=c[a[i][r]];                                          
            if (a[i][r]==a[j][r]) c[a[i][r]]++;         
        }           
    }
}
cout&lt;&lt;ans&lt;&lt;endl;
return 0;

}