首页 > ACM题库 > HDU-杭电 > hdu 2640 Toy bricks-动态规划-[解题报告]C++
2014
02-12

hdu 2640 Toy bricks-动态规划-[解题报告]C++

Toy bricks

问题描述 :

When Teddy was a child,he liked playing toy bricks very much.And he had found an interesting way to play with those toy bricks.
There is a big plate with some blocks in it,of course you can’t put the bricks in the block,you can only put the the bricks in the place which is empty.
To make the problem easier I only give you one kind of brick:

@
@@@
@

and I will give you the box’s initial state as below:


...####..
...###..#
..####..#
...####..

the ‘#’ means the block and the ‘.’ means the empty place.
To play this game,simply,you just need to put as many bricks to the box as you can.
OK,just tell me what is the maximum number of bricks can be put into the box ^_^.

输入:

The first line contain a T followed by T cases.
The first line of each case,there are two integers n,m,indicating the Height adn the Width of the box.(n <= 100 , m <= 8).
then n lines strings each with m characters give the initial stae of the box.
There will be one blank line after each case.

输出:

The first line contain a T followed by T cases.
The first line of each case,there are two integers n,m,indicating the Height adn the Width of the box.(n <= 100 , m <= 8).
then n lines strings each with m characters give the initial stae of the box.
There will be one blank line after each case.

样例输入:

1
5 4
#.#.
...#
#..#
#...
##.#

样例输出:

2

题目

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int t,n,m,dp[2][13][13],num,ok[13],cnt[13];
char map[105][10];

/*
    状态是每个物体的第三行...
    由于第二行的特殊性,加上不能重叠,可以知道第三行状态很少一共有:
    00000000 , 01001000
    01000000 , 01000100
    00100000 , 01000010
    00010000 , 00100100
    00001000 , 00100010
    00000100 , 00010010
    00000010
    13种.
*/
inline void init(){//求出合法状态
    ok[0]=cnt[0]=0;
    num=1;
    for(int i=1;i+1<m;i++){
        ok[num]=(1<<i),cnt[num]=1,num++;
        for(int j=i+3;j+1<m;j++){
            ok[num]=(1<<i)+(1<<j),cnt[num]=2,num++;
        }
    }
}

inline bool suit(int st,int i){//第i行状态为st,可以吗?需要考虑三行
    for(int j=0;j<m;j++){
        if(st&(1<<j)){
            if(map[i][j]=='#' || map[i-1][j]=='#' || map[i-1][j-1]=='#' || map[i-1][j+1]=='#' || map[i-2][j]=='#')
                return 0;
        }
    }
    return 1;
}

inline bool Can1(int st1,int st2){//对于物体,第三行的状态和第二行的状态合法不
    int a[3][8];
    memset(a,0,sizeof(a));
    for(int i=0;i<8;i++){
        if(st1&(1<<i)){
            a[0][i]++,a[1][i]++,a[1][i-1]++,a[1][i+1]++,a[2][i]++;
        }
        if(st2&(1<<i)){
            a[1][i]++,a[2][i]++,a[2][i-1]++,a[2][i+1]++;
        }
    }
    for(int i=0;i<8;i++){
        if(a[0][i]>1 || a[1][i]>1 || a[2][i]>1) return 0;
    }
    return 1;
}

inline bool Can2(int st1,int st2){//对于物体,第三行的状态和第一行的状态合法不
    for(int i=0;i<m;i++){
        if(st1&(1<<i)){
            if(st2&(1<<i)){
                return 0;
            }
        }
    }
    return 1;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) scanf("%s",map[i]);
        if(n<=2 || m<=2 ) puts("0");
        else{
            init();
            int now=0;
            memset(dp[now],0,sizeof(dp[now]));
            for(int i=2;i<n;i++){
                now^=1;
                memset(dp[now],0,sizeof(dp[now]));
                for(int j=0;j<num;j++){
                    int st1=ok[j];
                    for(int k=0;k<num;k++){
                        int st2=ok[k];
                        for(int r=0;r<num;r++){
                            int st3=ok[r];
                            if(!suit(st3,i)) continue;
                            if(!Can1(st3,st1)) continue;
                            if(!Can2(st3,st2)) continue;
                            dp[now][r][j]=max(dp[now][r][j],dp[1-now][j][k]+cnt[r]);
                        }
                    }
                }
            }
            int ans=0;
            for(int i=0;i<num;i++)
                for(int j=0;j<num;j++)
                    ans=max(ans,dp[now][i][j]);
            printf("%d\n",ans);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/zhuhuangjian/article/details/19077039


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  4. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

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