首页 > 搜索 > DFS搜索 > HDU 4478-Where is the King-动态规划-[解题报告]HOJ
2015
07-16

HDU 4478-Where is the King-动态规划-[解题报告]HOJ

Where is the King

问题描述 :

  There is a King placed on an N * N chessboard. In each second, Bob must move the King to the next cell in one of the eight directions, but he can not move the King to the outside of the chessboard, and can not move the King to a damaged cell. Note: If and only if there is not any next cell that he can place the King on in the eight directions, the King will stay in the same cell.
Now your task is to calculate that, after T seconds, the number of the cells that the King could be on.

输入:

  There is an integer C (1 <= C <= 500) in the first line, indicates there are C test cases in total.
  For each test case, there are four integers N (2 <= N <= 100), T (1 <= T <= 1000000000), X (1 <= X <= N), Y (1 <= Y <= N). N and T have the same meaning as above, (X, Y) indicates the King’s initial location. Then there are N lines. In each line, there is a string with N characters include “#” and “.”, which indicates the states of the cells in this row. “#” means this cell is damaged, and “.” means this cell is ordinary. You can assume (X, Y) is an ordinary cell.
  For the coordinate (x, y), it stands for the cell in row x and column y. The coordinate of the top-left cell is (1, 1), and the coordinate of the bottom-right cell is (N, N).

输出:

  There is an integer C (1 <= C <= 500) in the first line, indicates there are C test cases in total.
  For each test case, there are four integers N (2 <= N <= 100), T (1 <= T <= 1000000000), X (1 <= X <= N), Y (1 <= Y <= N). N and T have the same meaning as above, (X, Y) indicates the King’s initial location. Then there are N lines. In each line, there is a string with N characters include “#” and “.”, which indicates the states of the cells in this row. “#” means this cell is damaged, and “.” means this cell is ordinary. You can assume (X, Y) is an ordinary cell.
  For the coordinate (x, y), it stands for the cell in row x and column y. The coordinate of the top-left cell is (1, 1), and the coordinate of the bottom-right cell is (N, N).

样例输入:

3
3 1 3 3
...
...
...
3 2 3 3
...
..#
.#.
3 4 1 3
.#.
.##
...

样例输出:

3
6
1
Hint
For Sample 1, the blue cells in the left picture of the Figure 1 show the cells that the King could be on after 1 second.   For Sample 2, the blue cells in the right picture of the Figure 1 show the cells that the King could be on after 2 seconds. The red cells stand for the damaged cells, and the yellow cells shows other ordinary cells.
Cut the rope II

要求的两个人每一步最优的博弈 那么再某种状态下 当前步人所能走到的最优值是可以确定的

这一题在暴搜中还用到了记忆化 也就是换手的时候 那么当前步能走的就变成了 前一状态下 的最优值的负数

题目真的很不错 可惜我太水了

#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 99999999
int dp[(1<<21)+5],score[(1<<21)+5],g,b,s,x,y;
int bag[25][20];
void cal(){
    int sum[11];
    for(int i=0;i<(1<<b);++i){
        memset(sum,0,sizeof sum);
        for(int j=0;j<b;++j){
            if(i>>j&1){
                for(int k=1;k<=g;++k)sum[k]+=bag[j][k];
            }
        }
        for(int j=1;j<=g;++j)score[i]+=sum[j]/s;
    }
}

int dfs(int cur){
    if(dp[cur]!=-inf)return dp[cur];
    
    for(int j=0;j<b;++j)
        if(!(cur&(1<<j))){
            int res=score[cur|(1<<j)]-score[cur];
            if(res>0){
                dp[cur]=max(dp[cur],dfs(cur|(1<<j))+res);
            }else{
                dp[cur]=max(-dfs(cur|(1<<j)),dp[cur]);
            }
        }
    
    return dp[cur];
}

void solve(){
    memset(bag,0,sizeof bag);
    memset(score,0,sizeof score);
    for(int i=0;i<b;++i){
        scanf("%d",&x);
        while(x--){
            scanf("%d",&y);
            bag[i][y]++;
        }
    }
    cal();
    for(int i=0;i<(1<<b);++i)dp[i]=-inf;
    dp[(1<<b)-1]=0;
    printf("%d\n",dfs(0));
}
int main(){
    while(~scanf("%d%d%d",&g,&b,&s),g+b+s){
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ahjkl007/article/details/41108419