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

CF 253D(矩阵-4角相等且矩阵权值有上限的矩阵数）
D. 4a矩阵time limit per test2 secondsmemory limit per test256 megabytesinputinput.txtoutputoutput.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 4aabbbaabbaab

  output

  2

  input

  4 5 1ababaccacaccacbcbabc

  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%d\n",&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;}