首页 > 代码库 > 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); }}
hdu2870(dp求最大子矩阵)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。