首页 > ACM题库 > HDU-杭电 > HDU 3634-City Planning-分治-[解题报告]HOJ
2014
11-29

HDU 3634-City Planning-分治-[解题报告]HOJ

City Planning

问题描述 :

After many years, the buildings in HDU has become very old. It need to rebuild the buildings now. So Mr dragon (the president of HDU’s logistics department ) ask Mr Wan (a very famous engineer) for help.
Mr Wan only draw one building on a construction design drawings(all the buildings are rectangle and each edge of buildings’ is paraller or perpendicular to others buildings’ edge ). And total draw n drawings (all the drawings have same width and length . And bottomleft point is (0, 0)). Due to possible overlap of conditions, so when they build a new building, they should to remove all the overlapping part of it. And for each building, HDU have a jury evaluate the value per unit area. Now Mr dragon want to know how to arrange the order of build these buildings can make the highest value.

输入:

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20).
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings’ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)

输出:

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20).
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings’ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)

样例输入:

1
3
1 1 10 10 4
4 4 15 5 5
7 8 20 30 6

样例输出:

Case 1: 2047

这一题其实并不难,昨天比赛时WA了,下来请教了队友,原来是用的矩形切割

Problem 3634 62MS 224K

本题思路:以出现的矩形端点为交点将所有的矩形分割成一个个小矩形,这里的点要求不重复且升序,正好用到set很方便(相当于离散化)。

然后再把原来的矩形按照value的降序排列,将每个矩形所覆盖的且还没有着色小矩形块统统着色,并求价值和,即得结果。

查找矩形覆盖的小矩形块时可用二分,但本题数据规模较小,就线性扫描查找了。

另外,本题我刚开始定义结果为long long型,用G++提交WA了。后将结果定义为__int64,用C++交,闪亮AC!

#include<iostream>
#include<set>
using namespace std;
struct rect{
    int x1,y1,x2,y2,v;
}r[22];
set<int> col[2];
int map[50][50],xcol[50],ycol[50],xnum,ynum;
int cmp(const void *a,const void *b)
{
    struct rect *aa=(struct rect *)a;
    struct rect *bb=(struct rect *)b;
    return bb->v -aa->v;
}
int findx(int a)
{
    for(int i=0;i<xnum;i++)
        if(a==xcol[i])
            return i;
}
int findy(int a)
{
    for(int i=0;i<ynum;i++)
        if(a==ycol[i])
            return i;
}
int main()
{
    int cas,ca,n,i,j,k;
    __int64 ans;
    int sx,sy,ex,ey;
    scanf("%d",&cas);
    for(ca=1;ca<=cas;ca++)
    {
        col[0].clear(); 
        col[1].clear();
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2,&r[i].v);
            col[0].insert(r[i].x1); col[0].insert(r[i].x2);
            col[1].insert(r[i].y1); col[1].insert(r[i].y2);
        }
        qsort(r,n,sizeof(r[0]),cmp);
        memset(map,0,sizeof(map));
        xnum=ynum=0;
        set<int>::iterator it;
        for(it=col[0].begin();it!=col[0].end();it++)
            xcol[xnum++]=*it;
        for(it=col[1].begin();it!=col[1].end();it++)
            ycol[ynum++]=*it;
       /*for(i=0;i<xnum;i++)
            printf("%d ",xcol[i]);
        puts("");
        for(i=0;i<ynum;i++)
            printf("%d ",ycol[i]);
        puts("");*/

        printf("Case %d: ",ca);
        ans=0;
        for(i=0;i<n;i++)
        {
            sx=findx(r[i].x1);  ex=findx(r[i].x2);
            sy=findy(r[i].y1);  ey=findy(r[i].y2);
            //printf("%d %d %d %d \n",sx,xcol[sx],sy,ycol[sy]);
            //printf("%d %d %d %d \n",ex,xcol[ex],ey,ycol[ey]);
            //printf("%lld\n",(__int64)(r[i].v));
            for(j=sx;j<ex;j++)
            {
                for(k=sy;k<ey;k++){
                    if(map[j][k]==0)
                    {
                        map[j][k]=1;
                        ans+=(__int64)(xcol[j+1]-xcol[j])*(__int64)(ycol[k+1]-ycol[k])*(__int64)(r[i].v);
                        //printf("//%d %d %d %d\n",(xcol[j+1]-xcol[j]),(ycol[k+1]-ycol[k]),(r[i].v),ans);
                    }
                }
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

 昨天比赛做的是多校(十九),悲剧收场!提一下每题的大致意思吧,以后也好回忆……

3632 决斗问题 DP

3635 并查集 最简单的一题

3636 最优搜索

3637 在区间内找一个分子分母和最小的分数 数论

3638 应该也用搜索解决吧 怪兽的视野会移动 咬笔杆……

3639 老鹰捉小鸡 图论连通问题

参考:http://www.cnblogs.com/DreamUp/archive/2010/10/03/1841662.html


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false