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)
then your program would print the maximum number of points one can get by optimally distributing pebbles while respecting the two rules, which would be this (each output should be printed on a single line and followed with a newline):
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
1 //2017-08-02
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5
6 using namespace std;
7
8 int arr[22][22];
9 int dp[22][20000], sum[22][20000];//dp[i][j]表示第i行使用第j种方法所能得到的最大值，sum[i][j]表示第i行使用第j种方法所得的和
10 int state[20000];//表示可行的状态，即可行的取数方法
11 int len, n;
12
13 bool ok(int sta)//可行状态，即1的位置两两不相邻
14 {
15 return (sta&(sta<<1))==0 ? true : false;
16 }
17
18 int get_sum(int pos, int x)//求第pos行，使用x方法能取得的和
19 {
20 int sum = 0, cnt = 1;
21 while(x)
22 {
23 sum += (x%2)*arr[pos][n-cnt];
24 x >>= 1;
25 cnt++;
26 }
27 return sum;
28 }
29
30 void init(int m)//初始化
31 {
32 len = 0;
33 for(int i = 0; i < (1<<m); i++)
34 if(ok(i))state[len++] = i;
35 for(int i = 0; i < n; i++)
36 for(int j = 0; j < len; j++)
37 sum[i][j] = get_sum(i, state[j]);
38 memset(dp, 0, sizeof(dp));
39 for(int i = 0; i < len; i++)
40 dp[0][i] = sum[0][i];
41 }
42
43 void read(){
44 char str[200];
45 int row = 0;
46 while(cin.getline(str, 200)){
47 if(strlen(str) == 0)break;
48 for(int i = 0; i < strlen(str); i+=3){
49 arr[row][i/3] = (str[i]-‘0‘)*10+(str[i+1]-‘0‘);
50 }
51 row++;
52 }
53 n = row;
54 }
55
56 int main()
57 {
58 while(1)
59 {
60 read();
61 if(n == 0)break;
62 init(n);
63 for(int i = 1; i < n; i++)//处理第i行
64 for(int j = 0; j < len; j++)//采取第j种方法
65 for(int k = 0; k < len; k++)//枚举上一行所采取的方法k
66 if((state[j]&state[k])==0 && ((state[j]<<1)&state[k])==0 && ((state[j]>>1)&state[k])==0)//方法j、k可行。
67 dp[i][j] = max(dp[i][j], dp[i-1][k]+sum[i][j]);//状态转移方程
68
69 int ans = 0;
70 for(int i = 0; i < len; i++)//找出最大值
71 if(dp[n-1][i]>ans)
72 ans = dp[n-1][i];
73
74 cout<<ans<<endl;
75 }
76 return 0;
77 }
