首页 > ACM题库 > HDU-杭电 > hdu 2167 Pebbles-动态规划-[解题报告]C++
2013
12-30

hdu 2167 Pebbles-动态规划-[解题报告]C++

Pebbles

问题描述 :

You’re given an unlimited number of pebbles to distribute across an N x N game board (N drawn from [3, 15]), where each square on the board contains some positive point value between 10 and 99, inclusive. A 6 x 6 board might look like this:

The player distributes pebbles across the board so that:

?At most one pebble resides in any given square.
?No two pebbles are placed on adjacent squares. Two squares are considered adjacent if they are horizontal, vertical, or even diagonal neighbors. There’s no board wrap, so 44 and 61 of row three aren’t neighbors. Neither are 33 and 75 nor 55 and 92.

The goal is to maximize the number of points claimed by your placement of pebbles.

Write a program that reads in a sequence of boards from an input file and prints to stdout the maximum number of points attainable by an optimal pebble placement for each.

输入:

Each board is expressed as a series of lines, where each line is a space-delimited series of numbers. A blank line marks the end of each board (including the last one)

输出:

Each board is expressed as a series of lines, where each line is a space-delimited series of numbers. A blank line marks the end of each board (including the last one)

样例输入:

71 24 95 56 54
85 50 74 94 28
92 96 23 71 10
23 61 31 30 46
64 33 32 95 89

78 78 11 55 20 11
98 54 81 43 39 97
12 15 79 99 58 10
13 79 83 65 34 17
85 59 61 12 58 97
40 63 97 85 66 90

33 49 78 79 30 16 34 88 54 39 26
80 21 32 71 89 63 39 52 90 14 89
49 66 33 19 45 61 31 29 84 98 58
36 53 35 33 88 90 19 23 76 23 76
77 27 25 42 70 36 35 91 17 79 43
33 85 33 59 47 46 63 75 98 96 55
75 88 10 57 85 71 34 10 59 84 45
29 34 43 46 75 28 47 63 48 16 19
62 57 91 85 89 70 80 30 19 38 14
61 35 36 20 38 18 89 64 63 88 83
45 46 89 53 83 59 48 45 87 98 21

15 95 24 35 79 35 55 66 91 95 86 87
94 15 84 42 88 83 64 50 22 99 13 32
85 12 43 39 41 23 35 97 54 98 18 85
84 61 77 96 49 38 75 95 16 71 22 14
18 72 97 94 43 18 59 78 33 80 68 59
26 94 78 87 78 92 59 83 26 88 91 91
34 84 53 98 83 49 60 11 55 17 51 75
29 80 14 79 15 18 94 39 69 24 93 41
66 64 88 82 21 56 16 41 57 74 51 79
49 15 59 21 37 27 78 41 38 82 19 62
54 91 47 29 38 67 52 92 81 99 11 27
31 62 32 97 42 93 43 79 88 44 54 48

样例输出:

572
683
2096
2755

原题直通车:
HDU 2167 Pebbles

题意: 有个N*N( 3<=N<=15 )方阵, 可从中若干个数, 使其总和最大.

      取数要求, 当某一个数被选, 其周围8个数都不能选. 

分析: 第i行第j列的选数状态,不但影响到i+1行的j列取数状态,而且影响到j-1、j+1列的选数。

      如果只压缩为一种状态,判断可行性时不方便,所以我将其压缩成两种状态。

      状态X:将下一行不能选的位置都标1 (被选数位置、);

      状态Y:仅将被选数的位置标1;

      判断可行性:Y(i行) & X(i-1行) = 0 为可行,否则不行。

代码:

//125MS	408K	1718B	C++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<sstream>

#define max(a,b) a>b?a:b
using namespace std;
int n; 
int f[20],dp[16][1666];
int X[1666], Y[1666], num[1666];
// X[i]: 某行中取数状态,其下一行不能取的位置都标为1 (状态X)
// Y[i]: 取数的状态,将被取数的位置标1 (状态Y)
int len,a[20];  
void DFS(int k,int t,int c){
    if(c==t) {
        int u=0,v=0;   // u: 取了数的位置及左右两位置标1;   V: 取了数的位置标1
        for(int i=1;i<=t;++i)
            if(a[i]){
                v|=(1<<(i-1));  
                u|=(1<<(i-1));
                u|=(1<<i);
                if(i>1) u|=(1<<(i-2));
            }
            X[len]=u, Y[len]=v; ++len;
        return ;
    }
    for(int i=0;i<2;++i){
        if(i&&a[k-1]) continue;
        a[k]=i;
        DFS(k+1,t,c+1);
    }
}
int work(int x){                  // 计算某一状态在一行中取数的和
    int ret=0,i=1;
    while(x){
        if(x&1)ret+=f[i];
        x>>=1; ++i;
    }
    return ret;
}
void Init(char* ch){
    char x[10];
    stringstream in(ch);          // 截取空格分开的子串, 即提取每个整数
    n=len=0;                      // len状态种数
    while(in>>x) f[++n]=atoi(x);  // 把串转为整形
    DFS(1,n,0);
    memset(dp,0,sizeof(dp));
    for(int j=0; j<len; ++j)
        dp[1][j]=work(Y[j]);      // 第一行的状态Y做为dp方程初始化
}
int main(){
    char ch[150];
    while(gets(ch)!=NULL){
        Init(ch);
        int ans=0;
        for(int i=2;i<=n;++i){
            for(int j=1;j<=n;++j)
                scanf("%d",f+j);
            for(int j=0;j<len;++j)
                num[j]=work(Y[j]);     // num[j]: 第j种状态Y, 在i行取数的和
            for(int j=0; j<len; ++j)
                for(int k=0; k<len; ++k)
                    if(!(Y[j]&X[k])) { //用i行的状态Y匹配i-1行的状态X 等于0为可行
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+num[j]);
                        ans=max(dp[i][j],ans);
                    }
        }
        printf("%d\n",ans); 
        getchar(); 
        getchar();
    }
}

解题转自:http://blog.csdn.net/du489380262/article/details/9916347


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!