首页 > 代码库 > hdu2870(dp求最大子矩阵)

hdu2870(dp求最大子矩阵)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2870

 

分析:分别转换成‘a‘,‘b‘,‘c‘三种来求,其实就跟hdu1505一样了。。。

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30using namespace std;char s[1010][1010],str[1010][1010];int sum[1005][1005],l[1010],r[1010];int n,m;int solve(char ch,char a,char b,char c){    int t;    memset(sum,0,sizeof(sum));    for(int i=1; i<=n; i++)        for(int j=1; j<=m; j++)        {            if(s[i][j]==a||s[i][j]==b||s[i][j]==c)str[i][j]=ch;            else str[i][j]=s[i][j];        }    for(int i=1; i<=n; i++)        for(int j=1; j<=m; j++)        {            if(str[i][j]==ch)sum[i][j]=sum[i-1][j]+1;            else sum[i][j]=0;        }    int ans=-1;    for(int i=1; i<=n; i++)    {        l[1]=1;        r[m]=m;        for(int j=2; j<=m; j++)        {            t=j;            while(t>1&&sum[i][j]<=sum[i][t-1])t=l[t-1];            l[j]=t;        }        for(int j=m-1; j>=1; j--)        {            t=j;            while(t<m&&sum[i][j]<=sum[i][t+1])t=r[t+1];            r[j]=t;        }        for(int j=1; j<=m; j++)            ans=max(ans,(r[j]-l[j]+1)*sum[i][j]);    }    return ans;}int main(){    while(scanf("%d%d",&n,&m)>0)    {        for(int i=1;i<=n;i++)scanf("%s",s[i]+1);        int ans=-1;        ans=max(ans,solve(a,w,y,z));        ans=max(ans,solve(b,w,x,z));        ans=max(ans,solve(c,x,y,z));        printf("%d\n",ans);    }}
View Code

 

hdu2870(dp求最大子矩阵)