HDU 1505 City Game (hdu1506 dp二维加强版)

By | 11月21日
Advertisement

F - City Game

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 1505

Appoint description:

Description

Bob is a strategy game programming specialist. In his new city building game the gaming environment is as follows: a city is built up by areas, in which there are streets, trees,factories and buildings. There is still some space in the area that is unoccupied. The strategic task of his game is to win as much rent money from these free spaces. To win rent money you must erect buildings, that can only be rectangular, as long and wide as you can. Bob is trying to find a way to build the biggest possible building in each area. But he comes across some problems � he is not allowed to destroy already existing buildings, trees, factories and streets in the area he is building in.

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.

Input

The first line of the input contains an integer K � determining the number of datasets. Next lines contain the area descriptions. One description is defined in the following way: The first line contains two integers-area length M<=1000 and width N<=1000, separated by a blank space. The next M lines contain N symbols that mark the reserved or free grid units,separated by a blank space. The symbols used are:

R � reserved unit

F � free unit

In the end of each area description there is a separating line.

Output

For each data set in the input print on a separate line, on the standard output, the integer that represents the profit obtained by erecting the largest building in the area encoded by the data set.

Sample Input

2
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

Sample Output

45 0

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int d[1010][1010];
int l[1010];
int r[1010];
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
      //  memset(d,0,sizeof(d));
        for(int i=0; i<a; i++)
        {
            for(int j=0; j<b; j++)
            {
                char c[2];
                cin>>c;
                if(c[0]=='F')
                    d[i][j]=1;
                else
                    d[i][j]=0;
            }
        }
        /*
0 1 1 1 1 1                         0 1 1 1 1 1
1 1 1 1 1 1  (F=1,R=0,方便求和)    1 2 2 2 2 2
0 0 0 1 1 1  转化完就是右边矩阵     0 0 0 3 3 3
1 1 1 1 1 1                         1 1 1 4 4 4
1 1 1 1 1 1                         2 2 2 5 5 5
        */
        for(int i=1; i<a; i++)
        {
            for(int j=0; j<b; j++)
            {
                if(d[i][j]!=0)
                    d[i][j]=d[i-1][j]+1;
            }
        }
     /*   printf("--------------->\n");
        for(int i=0; i<a; i++){
            for(int j=0; j<b; j++)
                printf("%d ",d[i][j]);
            printf("\n");
        }

           printf("----------------->\n");*/
        int max=0;
        for(int i=0; i<a; i++){
            for(int j=0; j<b; j++){
                l[j]=j;
                while(l[j]>0&&d[i][l[j]-1]>=d[i][j])
                       l[j]=l[l[j]-1];
            }
            for(int j=b-1; j>-1; j--){
                r[j]=j;
                while(r[j]<b-1&&d[i][r[j]+1]>=d[i][j])
                    r[j]=r[r[j]+1];
            }
            for(int j=0; j<b; j++)
                if(max<((r[j]-l[j]+1)*d[i][j]))
                    max=((r[j]-l[j]+1)*d[i][j]);
        }
        cout<<max*3<<endl;
    }
    return 0;
}

Similar Posts:

  • hdu 1505 City Game 1506的二维

    City Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4258 Accepted Submission(s): 1779 Problem Description Bob is a strategy game programming specialist. In his new city building game the gam

  • Hdu 2888 Check Corners (数据结构_二维RMQ)

    Hdu 2888 Check Corners (数据结构_二维RMQ) 分类: 全部博客 ACM_好题经典题2012-07-24 10:40 264人阅读 评论(0) 收藏 举报 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2888 题目大意:给定一个n * m的矩阵,再给定q个询问,每次询问(r1,c1)为左上角,(r2,c2)为右下角的子矩形的最大值. 解题思路:很常规的二维RMQ查询最大值.第一次写二维rmq,现在来理下思路. 二维RMQ是

  • HDU 1024 Max Sum Plus Plus(二维数组转化为一维数组)

    Problem Description: Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem. Given a consecutive number seq

  • hdu 3496 Watch The Movie(二维费用的 01背包)

    题目:有n集卡通,每一集的时间为t[i],价值为v[i],选择m集,要在l时间内看完,问如何选择可以使家孩子最大. 分析:很裸的二维费用的背包,吧时间看成一维,集数看成一维,定义dp[i][j][k]为选择前i集,用j时间,看k集,所得的最大费用. 状态转移方程为:dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-t[i]][k-1]+v[i]); 初始化:dp[i][j][0]=0,看0集所得价值为0: 其他的其它的为非法.... 注意:看的集数k逆序 顺序都能过

  • HDU 3496 Watch The Movie(二维背包)

    Watch The Movie Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 7105    Accepted Submission(s): 2244 Problem Description New semester is coming, and DuoDuo has to go to school tomorrow. She dec

  • hdu 1505 City Game(0和1 中的最大子矩阵)

    City Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3834 Accepted Submission(s): 1588 Problem Description Bob is a strategy game programming specialist. In his new city building game the gam

  • HDU 3496 Watch The Movie【二维费用的0/1背包问题】

    思路: 要注意的几点: (1)必须要在N种动漫里面选择M种,所以初始化时dp[L][M]时,除当m=0,dp[L][M]=0外,其他的初始化为负的无穷大:(见背包九讲关于初始化得方法) (2)最后输出时要满足dp[L][M]不小于0,因为当dp[L][M]<0时,表明不可能在N种动漫里面选择M种(无法完全满足),也是题意:"If DuoDuo can't watch all of the movies that her uncle had bought for her, please ou

  • hdu 1505 city game (1506 加强版)

    #include<iostream> #include<cstdio> #include<cstring> using namespace std; char ss[33]; int b[1002][1002],qian[1002],hou[1002]; int main() { int i,j,n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m);

  • hdu 1176 免费馅饼 二维dp

    原文地址 设a[i][j]为第i秒的j位置掉下的馅饼数量,f[i][j]为第i秒在j位置接馅饼最多可以接到的最多馅饼数量.由于每秒只能移动一个位置,因此这一状态可能由三种情况达到: f[i - 1][j - 1] f[i - 1][j] f[i - 1][j + 1] 这三种情况中的最大值加上当前位置可以接到的馅饼数即是当前位置可以接到的最大馅饼数量: f [ i ] [ j ] = max ( f [ i - 1 ] [ j - 1 ] , f [ i - 1 ] [ j ] , f [ i 

  • HDU 3127 WHUgirls【二维完全背包】

    题意:给出一个长为a,宽为b的布,再给出n个围巾的规格(长x,宽y,价值c),问怎样裁剪能够得到最大的价值. ----第一次做的时候不会---然后放到今天做--发现还是不会---于是又--看题解了----@_@=== 因为相同规格的围巾可以重复剪多次,且围巾的长和宽相当于两个约束,所以可以转换为二维费用的完全背包问题. 然后就是围巾的裁剪 第一种 横着减 裁切线分为两种 对于左上的第一个图,当减去长为x,宽有长为y的一个矩形之后,剩余的面积之和分别由长为i-x,宽为y:长为i,宽为j-y的两个矩

Tags: