902
cf 154.div2 D. Table with Letters - 2
今天的比赛题比较奸诈，居然是文件读入的，让A题耽误了很多时间。
这题是dp的一个经典类型，o((n*m)^2)的算法非常好写，但是必然TLE。因为其要求四角均相等，不妨以此为条件进行判断，即可缩为o(n^2*m)算法
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int sum[402][402];
char a[402][402];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int m,n,K,i,j,t;
scanf("%d%d%d",&n,&m,&K);
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++)
{
getchar();
for(j=1;j<=m;j++)
{
a[i][j]=getchar();
sum[i][j]=0-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1];
if(a[i][j]=='a')sum[i][j]++;
}
}
long long ans=0;
int now[257],k,p;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
memset(now,0,sizeof(now));
for(k=1,p=1;k<=m;k++)
{
if(a[i][k]!=a[j][k])continue;
now[a[i][k]]--;
// if(p==1)p=k;
//cout<<now[a[i][k]]<<endl;
while(p<=m&&sum[j][p]+sum[i-1][k-1]-sum[i-1][p]-sum[j][k-1]<=K)
{
if(a[i][p]==a[j][p])now[a[i][p]]++;
p++;
}
if(now[a[i][k]]>0)ans+=now[a[i][k]];
//cout<<now[a[i][k]]<<" --------"<<endl;
}
}
cout<<ans<<endl;
}
最后更新：2017-04-02 00:06:52