HDU 2870 DP 最大完全子矩阵

本文主要是介绍HDU 2870 DP 最大完全子矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 1505 升级版

枚举a，b，c  各做一遍最大完全子矩阵

#include "stdio.h"
#include "string.h"char a[1010][1010];
int n,m,ans;
int sum[1010][1010];int max(int a,int b)
{if (a<b) return b;else return a;
}
void solve(char key)
{int i,j;int le[1010],ri[1010];memset(sum,0,sizeof(sum));for (i=0; i<n; i++)for (j=0; j<m; j++){if (key=='a' && (a[i][j]=='w' || a[i][j]=='y' || a[i][j]=='z' || a[i][j]=='a'))  sum[i][j]=sum[i][j-1]+1;if (key=='b' && (a[i][j]=='w' || a[i][j]=='x' || a[i][j]=='z' || a[i][j]=='b'))  sum[i][j]=sum[i][j-1]+1;if (key=='c' && (a[i][j]=='x' || a[i][j]=='y' || a[i][j]=='z' || a[i][j]=='c'))  sum[i][j]=sum[i][j-1]+1;}for (j=0; j<m; j++){for (i=0; i<n; i++)le[i]=ri[i]=i;for (i=0; i<n; i++)while (sum[i][j]<=sum[le[i]-1][j] && le[i]>0)le[i]=le[le[i]-1];for (i=n-1; i>=0; i--)while (sum[i][j]<=sum[ri[i]+1][j] && ri[i]<n-1)ri[i]=ri[ri[i]+1];for (i=0; i<n; i++)ans=max(ans,(ri[i]-le[i]+1)*sum[i][j]);}}
int main()
{int i;while (scanf("%d%d",&n,&m)!=EOF){getchar();for (i=0; i<n; i++)gets(a[i]);ans=0;solve('a');solve('b');solve('c');printf("%d\n",ans);}
}

这篇关于HDU 2870 DP 最大完全子矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---