点击打开链接uva 1330
思路:悬线法求解最大子矩阵
分析:
1 详细资料请见点击打开链接
2 有个地方需要注意的是输入格式,有可能输入字母后面会有多个空格,所以必须要过滤掉这些空格
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
int mat[MAXN][MAXN];
int up[MAXN][MAXN] , Left[MAXN][MAXN] , Right[MAXN][MAXN];
int n , m;
int solve(){
int ans = 0;
int leftNum , rightNum;
for(int i = 1 ; i <= n ; i++){
//从左往右求最大的左边列编号
leftNum = 0;
for(int j = 1 ; j <= m ; j++){
if(!mat[i][j]){
up[i][j] = 0;
Left[i][j] = 0;
leftNum = j;
}
else{
up[i][j] = i == 1 ? 1 : up[i-1][j]+1;
Left[i][j] = i == 1 ? leftNum+1 : max(Left[i-1][j] , leftNum+1);
}
}
//从右往左求最小的右边列编号
rightNum = m+1;
for(int j = m ; j >= 1 ; j--){
if(!mat[i][j]){
Right[i][j] = m+1;
rightNum = j;
}
else{
Right[i][j] = i == 1 ? rightNum-1 : min(Right[i-1][j] , rightNum-1);
ans = max(ans , up[i][j]*(Right[i][j]-Left[i][j]+1));
}
}
}
return 3*ans;
}
int main(){
int Case;
char c;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= m ; j++){
c = getchar();
while(c != 'F' && c != 'R')
c = getchar();
mat[i][j] = c == 'F' ? 1 : 0;
}
}
printf("%d\n" , solve());
}
return 0;
}
分享到:
相关推荐
[UVA10409] DieGame
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
##Game 这是游戏屏幕的模型,其中您的角色是左下角的灰色矩形。 因此,您可以通过按下左下角的按钮来让这个“运行”。 屏幕右下角的按钮代表您的角色可以进行的不同类型的攻击(/防御)。 ##Attacks 通过
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva_trilearn2002 源代码
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
PDF试题
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。