hdu1505City Game(动态规划)
City Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8359 Accepted Submission(s): 3630
Each area has its width and length. The area is divided into a grid of equal square units.The rent paid for each unit on which you're building stands is 3$.
Your task is to help Bob solve this problem. The whole city is divided into K areas. Each one of the areas is rectangular and has a different grid size with its own length M and width N.The existing occupied units are marked with the symbol R. The unoccupied units are marked with the symbol F.
R – reserved unit
F – free unit
In the end of each area description there is a separating line.
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
5 5
R R R R R
R R R R R
R R R R R
R R R R R
R R R R R
题意:给出一个矩阵,上面是可以用的土地和不能用的土地,要在上面选一块矩形的土地建房子,问最大能选多大的土地,土地每单位3块大洋,最后输出租金
核心是动态规划做的。
#include<bits/stdc++.h>
using namespace std;
int a[][];
int l[],r[];
int main()
{
int k;
while(~scanf("%d",&k))
{
int m,n;
while(k--)
{
scanf("%d %d",&m,&n);
memset(a,,sizeof(a));
for(int i=; i<m; i++)
{
for(int j=; j<n; j++)
{
char c[];//以后输入字符 中间带空格的题目都可以直
cin>>c; // 接输入字符数组
if(c[]=='F') a[i][j]=;
}
}
for(int i=; i<m; i++)
{
for(int j=; j<n; j++)
{
if(a[i][j]!=) a[i][j]=a[i-][j]+;
}
}
int max=;
for(int i=; i<m; i++)//一行一行找过去,求最大面积
{
for(int j=; j<n; j++)
{
l[j]=j;
while(l[j]>&&a[i][l[j]-]>=a[i][j]) l[j]=l[l[j]-];//向左边,当前l[j]继承符合要求的前
} // 一个的左边界,动态规划的核心,因为前一个
for(int j=n-; j>-; j--) //点的高度大于当前点,所以前一个点的左边界,当前点可以直接继承使用
{
r[j]=j;
while(r[j]<n-&&a[i][r[j]+]>=a[i][j]) r[j]=r[r[j]+];//向右边,思路和左边界一样
}
for(int j=; j<n; j++)
if(max<((r[j]-l[j]+)*a[i][j])) max=((r[j]-l[j]+)*a[i][j]);//表示从当前点向左右延伸的矩形面积
}
printf("%d\n",max*);//每单位面积3块大洋 } }
return ;
}
最新文章
- 【深入理解计算机系统02】ISA 与内存模型
- ReferenceQueue<;T>;随笔
- 学习OpenCV——行人检测&;人脸检测(总算运行出来了)
- [GraphQL] Use GraphQL&#39;s List Type for Collections
- BurpSuite实例教程
- PayPal 开发详解(三):在网站上创建【立即付款】按钮
- 【转载】使用Axure制作App原型怎样设置尺寸?
- C# 实现关闭按钮隐藏窗体而不退出
- spring配置文件位置
- java 连接sql server2008配置
- winmd文件和dll文件的区别
- Struts2_2_第一Struts2应用
- 基于ElementUI的网站换主题的一些思考与实现
- freeRTOS与裸机程序相比有什么区别??
- centos7升级内核版本
- 廖雪峰Java5集合-4Set-1使用Set
- Scrapy学习篇(二)之常用命令行工具
- Oracle 12C -- Unified Auditing Policy
- CSharp程序员学Android开发---3.Android内部元素不填充BUG
- Python 中的线程-进程2