首页 > 搜索 > DFS搜索 > hdu 2461 Rectangles-动态规划-[解题报告]C++
2014
01-26

hdu 2461 Rectangles-动态规划-[解题报告]C++

Rectangles

问题描述 :

You are developing a software for painting rectangles on the screen. The software supports drawing several rectangles and filling some of them with a color different from the color of the background. You are to implement an important function. The function answer such queries as what is the colored area if a subset of rectangles on the screen are filled.

输入:

The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 20) and M(1 ≤ M ≤ 100000), indicating the number of rectangles on the screen and the number of queries, respectively.
The i-th line of the following N lines contains four integers X1,Y1,X2,Y2 (0 ≤ X1 < X2 ≤ 1000, 0 ≤ Y1 < Y2 ≤ 1000), which indicate that the lower-left and upper-right coordinates of the i-th rectangle are (X1, Y1) and (X2, Y2). Rectangles are numbered from 1 to N.
The last M lines of each test case describe M queries. Each query starts with a integer R(1<=R ≤ N), which is the number of rectangles the query is supposed to fill. The following list of R integers in the same line gives the rectangles the query is supposed to fill, each integer of which will be between 1 and N, inclusive.

The last test case is followed by a line containing two zeros.

输出:

The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 20) and M(1 ≤ M ≤ 100000), indicating the number of rectangles on the screen and the number of queries, respectively.
The i-th line of the following N lines contains four integers X1,Y1,X2,Y2 (0 ≤ X1 < X2 ≤ 1000, 0 ≤ Y1 < Y2 ≤ 1000), which indicate that the lower-left and upper-right coordinates of the i-th rectangle are (X1, Y1) and (X2, Y2). Rectangles are numbered from 1 to N.
The last M lines of each test case describe M queries. Each query starts with a integer R(1<=R ≤ N), which is the number of rectangles the query is supposed to fill. The following list of R integers in the same line gives the rectangles the query is supposed to fill, each integer of which will be between 1 and N, inclusive.

The last test case is followed by a line containing two zeros.

样例输入:

2  2
0 0 2 2
1 1 3 3
1 1
2 1 2
2 1
0 1 1 2
2 1 3 2
2 1 2
0 0

样例输出:

Case 1:
Query 1: 4
Query 2: 7

Case 2:
Query 1: 2

做了差不多一天,终于过

题意:

就是给你NN<=20)个矩阵,共有M(M<=100000)个询问,每个询问就是涂r个矩阵,问总共有多少个单位矩阵被涂了。

开始时,其实就是一个容斥定理,总个数=所有的矩阵的面积重合两次的面积 +
重合三次的面积。。。。。

我用想到的直接用dp[N][N]来求dp[i][j]表示i表示宽度,第j矩阵到第j+i矩阵的重合,打了一下代码,发现完全错误了,其实要求任意个矩阵的重合,不一定是连续的。想到这里,N十分小,而M十分大,就采用了状态压缩,每一矩阵用一位二进制表示总共有(1<<N)种状态。先预处理,将所有的情况都求出来。询问时,直接一个暴搜,将所有的组合求出来,分别记录在c数组中,c[i]表示i个矩阵重合的单位矩阵个数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 21
struct node
{
    int c,x1,x2,y1,y2;//c表示是否重合,1重合,0不重合
}co[N],a[1<<N];
int fa[1<<N],b[N];
int f[N+10];
int c[N];
void in()
{
    f[0]=1;
    for(int i=1;i<=20;i++) f[i]=f[i-1]*2;
}
int zhao(int &x,int &y,int x1,int y1,int x2,int y2)
{

    if(x1>x2) swap(x1,x2),swap(y1,y2);
    if(x2>=y1) return 0;
    else
    {
        x=x2;
        y=MIN(y1,y2);
    }
    return 1;
}
void find(int t,int i,int j)
{
    int c1,c2;
    c1=zhao(a[t].x1,a[t].x2,a[i].x1,a[i].x2,co[j].x1,co[j].x2);
    c2=zhao(a[t].y1,a[t].y2,a[i].y1,a[i].y2,co[j].y1,co[j].y2);
    a[t].c=c1&c2;
    j=t;
}
void init(int n)
{
    int i,j;
    a[0].x1=a[0].y1=0;
    a[0].x2=a[0].y2=1000;
    a[0].c=1;
    for(i=1;i<f[n];i++) a[i].c=0;
    memset(fa,0,sizeof(fa));
    for(i=0;i<f[n];i++)
        if(a[i].c)
        {
            for(j=0;j<n;j++)
                if((i&f[j])==0&&fa[i+f[j]]==0)
                {
                    fa[i+f[j]]=1;
                    find(i+f[j],i,j);
                }
        }
}
void dfs(int temp,int x,int n,int num)
{
    for(int i=x;i<n;i++)
    {
        int j=temp+f[b[i]];
        if(a[j].c)
        {
            c[num]+=(a[j].x2-a[j].x1)*(a[j].y2-a[j].y1);
            dfs(j,i+1,n,num+1);
        }
    }
}
int main()
{
    in();
    int cases=1,n,m;
    while(~scanf("%d%d",&n,&m)&&n+m)
    {
        int i,j,r,index;
        for(i=0;i<n;i++)
            scanf("%d%d%d%d",&co[i].x1,&co[i].y1,&co[i].x2,&co[i].y2);
        init(n);//预处理,将所有的情况求出来
        printf("Case %d:\n",cases++);
        for(int k=1;k<=m;k++)
        {
            int sum=0;
            scanf("%d",&r);
            for(i=0;i<r;i++)
            {
                scanf("%d",&b[i]);
                b[i]--;
                sum+=(co[b[i]].x2-co[b[i]].x1)*(co[b[i]].y2-co[b[i]].y1);
            }
            memset(c,0,sizeof(c));
            dfs(0,0,r,1);
            int mul=-1;
            for(i=2;i<=r;i++)
            {
                sum+=c[i]*mul;
                mul*=-1;
            }
            printf("Query %d: %d\n",k,sum);
        }
        printf("\n");
    }
    return 0;
}

解题转自:http://blog.csdn.net/tianjiewang/article/details/7723434


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。