hdu2870(dp求最大子矩阵)
2024-10-20 11:54:08
题目链接: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<<30
using namespace std;
char s[][],str[][];
int sum[][],l[],r[];
int n,m;
int solve(char ch,char a,char b,char c)
{
int t;
memset(sum,,sizeof(sum));
for(int i=; i<=n; i++)
for(int j=; 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=; i<=n; i++)
for(int j=; j<=m; j++)
{ if(str[i][j]==ch)sum[i][j]=sum[i-][j]+;
else sum[i][j]=;
}
int ans=-;
for(int i=; i<=n; i++)
{
l[]=;
r[m]=m;
for(int j=; j<=m; j++)
{
t=j;
while(t>&&sum[i][j]<=sum[i][t-])t=l[t-];
l[j]=t;
}
for(int j=m-; j>=; j--)
{
t=j;
while(t<m&&sum[i][j]<=sum[i][t+])t=r[t+];
r[j]=t;
}
for(int j=; j<=m; j++)
ans=max(ans,(r[j]-l[j]+)*sum[i][j]);
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)>)
{
for(int i=;i<=n;i++)scanf("%s",s[i]+);
int ans=-;
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);
}
}
最新文章
- html5新增标签和属性
- MipMap
- python 进程间共享数据 (二)
- 【QT】C++ GUI Qt4 学习笔记3
- SQL升级脚本实现按版本差异化升级(优化)
- 二模01day1解题报告
- DB天气app冲刺二阶段第十天
- call 方法在使用一个指定的this值和若干个指定的参数值的前提下调用某个函数或方法.
- 关于html页面图片自动撑开的问题
- 第五、六章:图像&;链接
- language-detection 语言检测工具 java版的应用demo
- C# 正则表达式应用
- MS17-010 漏洞研究——免考课题 20155104 赵文昊
- hdu 1503 Advanced Fruits(LCS输出路径)
- 费马定理&;欧拉定理
- 如何为一个类型为Color的属性设置默认值
- jconsole工具使用----jvm内存泄漏问题
- [转]Go与C语言的互操作
- QT STUDY 模型-视图-控制器
- Spring Tools Suite (STS) 简介
热门文章
- Fragment与FragmentActivity通信封装
- 基于visual Studio2013解决面试题之0604O(1)时间复杂度删除链表节点
- OpenCV中遇到Microsoft C++ 异常 cv::Exception
- Design Pattern Chain of Reponsibility 责任链模式
- EXT2/EXT3文件系统(一)
- Servlet的学习之Session(5)
- QNX---- interrupts 例程
- android花屏效果的实现(ViewPager的基本使用)
- Eclipse中导入第三方源码的问题和备用解决方案
- 怎样使用CMenu类