首页 > ACM题库 > HDU-杭电 > Hdu 1666 The Floor Bricks-剪枝&状态压缩[解题报告]C++
2013
12-21

Hdu 1666 The Floor Bricks-剪枝&状态压缩[解题报告]C++

The Floor Bricks

问题描述 :

Robert decided to decorate his new room with a cool pattern on the floor, composed with colorful floor bricks. After several days’ work, he finally felt satisfied with the pattern he created with the odd shaped bricks. Soon, he found a problem. As the border of the pattern is not a perfect rectangle, the floor is not filled with bricks completely. However, since the shapes of the bricks are quite odd, it is not an easy work to fill the floor with these bricks completely. (Although a brick with a unit size is provided, this kind of brick is quite expensive usually. Fig.1 shows an example of a set of bricks) As Robert was very proud of his brick pattern, he refuses to modify even one brick in his pattern in order to satisfy the need of filling the floor completely. Instead, he asked you to find solutions for him to fill the rest part of the floor completely with the given bricks so that the Gils needed to buy these bricks are minimized. Of course, the bricks can not overlap each other to fill the floor. Please note that the bricks can be rotated, but cannot be flipped over. In addition, you may assume that all kinds of bricks can be contained within a 3×3 square box.
 
As the pattern of bricks covers most areas of the floor, the uncovered part of the floor is actually located at the bottom border of the rectangular shaped floor. Therefore, an uncovered part like the one in Fig.2 can be described with a series of integers, which represents the number of square blocks missed in each column, starting from the left. Thus, the shape in Fig.2 can be described with 11 integers: 2 2 1 2 3 5 2 3 3 4 1. In addition, you may assume that these integers are no larger than 5. Fig.3 shows a solution to fill the floor with the brick set in Fig.1 that costs minimal Gils.

输入:

The input consists of at most 20 test cases. The first line of each test case contains an integer n ( 1<=n<=1000), which is the width of the floor. The second line contains n integers, separated by single spaces. These integers describe the shape of the uncovered floor as mentioned above. The third line contains an integer m ( 1<=m<=100), which is the number of bricks available. After this is the detailed description of the m bricks.Each bick description consists of 4 lines. The first line is a positive integer, which is the price of that brick in Gils. After this line, there are three lines, each consisting of three characters, which describe the shape of the brick. A dot character represents a space in the shape and a sharp character # represents a square block in the shape. You can be sure that the blocks are always connected to form the brick.There is a line containing a zero after the last test case, which signifies the end of the input and should not be processed.

输出:

For each test case, output a line `Need at least g Gil(s).’, where g is the minimal Gils needed to fill the floor with the given bricks. If the floor cannot be filled with the given bricks, output `Impossible.’ instead. Do not output blank lines between cases.

样例输入:

11
1 4 3 3 2 5 3 2 1 2 2
4
2
#..
#..
##.
3
.#.
.##
.#.
5
...
#..
##.
9
...
.#.
...
1
1
1
1
..#
...
...
1
1
1
1
.##
...
...
0

样例输出:

Need at least 28 Gil(s).
Need at least 1 Gil(s).
Impossible.

很纠结的题目,思路不是自己想出来的,技巧也是借鉴过来的,没想过搜索可以这样剪枝,不过还真学到些技巧。写dfs时用了一个全局变量导致程序异常,恁是调了两小时才揪出来,那是相当的郁闷啊。

ACcode:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

const int W=5;
const int MS=15;
const int MSK=1<<MS;
const int NS=1100;
const int INF=0x3f3f3f3f;

struct node{
    int sta,add;
}z;

char pic[4][4];
int n,m,w;
int tmp,top,num;
int p[3][3],q[3][3];
int bv[MSK],vis[MSK],best[MSK];
int h[NS],state[NS],value[NS][1<<10];
vector<node> tst[MSK];

int Trans_num(int arr[3][3])
{
    int st=0;
    for (int i=0;i<3;i++)
    for (int j=0;j<3;j++)
    st|=arr[i][j]<<(i*5+j);
    while ( !(st&31) ) st>>=5;
    while ( !(st&0x421) ) st>>=1;
    return st;
}

void Route()
{
    memcpy(q,p,sizeof(q));
    for (int i=0;i<3;i++)
    for (int j=0;j<3;j++)
    p[i][j]=q[2-j][i];
}

void dfs(int cur,int pre,int pos,int add)
{
    if(add>=best[pre]) return;
    best[pre]=add;
    if ( !(pre&31) )
    {
        z.sta=(pre>>5),z.add=add;
        tst[cur].push_back(z);
        return ;
    }
    for (int i=pos;i<top;i++)
    {
        int stu=state[i];
        do
        {
            if ( (pre&stu)==stu )
            dfs(cur,pre^stu,i,add+bv[i]);
            stu<<=1;
        }while( !(stu&0x421) );
    }
}

int cal(int pos,int st)
{
    if (value[pos][st]>=0) return value[pos][st];
    int r=INF,cur=st|(((1<<h[pos+2])-1)<<10);
    if (!vis[cur])
    {
        vis[cur]=1;
        memset(best,0x3f,sizeof(best));
        tst[cur].clear(),dfs(cur,cur,0,0);
    }
    for (int i=0;i<tst[cur].size();i++)
    r=min(r,cal(pos+1,tst[cur][i].sta)+tst[cur][i].add);
    return value[pos][st]=r;
}

void solve()
{
    memset(value,-1,sizeof(value));
    memset(vis,0,sizeof(vis)),value[n][0]=0;
    int ans=cal(0,((1<<h[0])-1)|(((1<<h[1])-1)<<5));
    if (ans>=INF) printf("Impossible.\n");
    else printf("Need at least %d Gil(s).\n",ans);
}

int main()
{
    while (~scanf("%d",&n)&&n)
    {
        top=0;
        memset(h,0,sizeof(h));
        memset(bv,0x3f,sizeof(bv));
        for (int i=0;i<n;i++)
        scanf("%d",&h[i]);
        scanf("%d",&m);
        for (int i=0;i<m;i++)
        {
            scanf("%d",&w);
            for (int j=0;j<3;j++)
            {
                scanf("%s",pic[j]);
                for (int k=0;k<3;k++)
                p[j][k]= (pic[j][k]=='#');
            }
            tmp=Trans_num(p);
            bv[tmp]=min(bv[tmp],w);

            for (int j=0;j<3;j++)
            {
                Route();
                tmp=Trans_num(p);
                bv[tmp]=min(bv[tmp],w);
            }
        }
        for (int i=1;i<MSK;i++)
        if (bv[i]<INF)
        state[top]=i,bv[top++]=bv[i];
        solve();
    }
    return 0;
}

转自:http://blog.csdn.net/cxsmile/article/details/9391839


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?