[暴力]餐桌

2024-01-30 06:32
文章标签 暴力 餐桌

本文主要是介绍[暴力]餐桌,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

你家刚买了一套新房,想邀请朋友回来庆祝,所以需要一个很大的举行餐桌,餐桌能容纳的人数等于餐桌的周长,你想买一个能容纳最多人的餐桌,餐桌的边必须跟房间的边平行。
给你的房间的设计,计算最多能邀请的客人数。

Input

第一行包含两个整数R和C(1<=R,C<=2000),表示房子的长和宽。
接下来R行每行S个字符(中间没有空格),“.”表示空白区域,“X”表示有障碍物,餐桌所占区域必须是空白的。

Output

输出最多能要求的客人数量。

Sample Input

输入1:
2 2
..
..

输入2:
4 4
X.XX
X..X
..X.
..XX

输入3:
3 3
X.X
.X.
X.X

Sample Output

输出1:
7

输出2:
9

输出3:
3

Data Constraint

Hint

【数据规模】
50%的数据R,C<=400
70%的数据R,C<=1000
100%的数据,R,C<=2000

分析

这题相当奇妙,其实只用搞一个前缀和然后暴力枚举开始点,然后取最大值(具体为什么不超时我也不知道,我也很难讲清,看程序吧)
时间复杂度分摊:O(kn^2)(k是数据中横向间隔的最大数)

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (i=a;i<=b;i++)
using namespace std;
int r,c;
int f[2001][2001];
void init()
{int i,j;char q;scanf("%d%d",&r,&c);rep(i,1,r)rep(j,1,c){do{scanf("%c",&q);}while (q!='.'&&q!='X');if (q!='X') f[i][j]=f[i-1][j]+1;}
}
void doit()
{int i,j,k,s,ans=0;rep(i,1,r)rep(j,1,c){s=f[i][j];k=j+1;while (f[i][k]!=0&&k<=c){ans=max(ans,(s+k-j)*2-1);s=min(s,f[i][k]);k++;}ans=max(ans,(s+k-j)*2-1);}printf("%d",ans);
}
int main()
{init();doit();
}

这篇关于[暴力]餐桌的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/659366

相关文章

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

10125-Sumsets【暴力】

利用n^2的时间枚举所有a[i] + a[j] 利用n^2的时间枚举所有a[i] - a[j] 之后利用n^2时间一个一个找a[i] - a[j]的值是否存在于a[i] + a[j]中 找的时候需要二分查找 另外一点就是注意long long的范围以及四个数是集合内不同的四个元素 15222638 10125 Sumsets Accepted C++ 0.449 2015-03-

10730-Antiarithmetic?【暴力枚举】

水题 求一个序列是否存在3个数按顺序构成等差数列 直接枚举等差数列的差值 时间复杂度降到 n * n / 3 开pos数组记录每个值得为之 楷vis数组记录目前i是否出现过 强行AC 15221397 10730 Antiarithmetic? Accepted C++ 0.035 2015-03-26 12:09:56 #include<cstdio>#include

HLJUOJ1125(暴力三点一线)

两点确定一条直线 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 19   Solved: 11 [ Submit][ Status][ Web Board] Description  给一个15000 * 15000 的区域, 坐标都是整数. 其中有N个点,N <= 770.问总共有多少个3点共线的组合.并按升序(点的ID)输出

HLJUOJ1117(暴力模拟)

八数码 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 109   Solved: 19 [ Submit][ Status][ Web Board] Description 给定一个8数码的初始状态,然后给出一系列对8数码的操作,求其最终状态. Input 第一行t,代表样例个数。 每组数据前三行各三个数,代表八数

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

UVA10010(八方向暴力枚举)

Where's Waldorf? Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu 题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18656 Description Where's Waldo

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There

CF#278 (Div. 2) A.(暴力枚举)

A. Giga Tower time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/A Giga To

CF#284 (Div. 2) B.(暴力)

题目链接:http://codeforces.com/contest/499/problem/B 解题思路: 开一个is变量记录每组单词最后应该输出哪个。最后每次把原来的数组暴力扫一遍即可。 完整代码: #include <functional>#include <algorithm>#include <iostream>#include <fstream>#inc