You're given an unlimited number of pebbles to distribute across an N x N game board (N drawn from 

3,153,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. 

InputEach 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)

Outputthen 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): 

Sample Input

71 24 95 56 5485 50 74 94 2892 96 23 71 1023 61 31 30 4664 33 32 95 8978 78 11 55 20 1198 54 81 43 39 9712 15 79 99 58 1013 79 83 65 34 1785 59 61 12 58 9740 63 97 85 66 9033 49 78 79 30 16 34 88 54 39 2680 21 32 71 89 63 39 52 90 14 8949 66 33 19 45 61 31 29 84 98 5836 53 35 33 88 90 19 23 76 23 7677 27 25 42 70 36 35 91 17 79 4333 85 33 59 47 46 63 75 98 96 5575 88 10 57 85 71 34 10 59 84 4529 34 43 46 75 28 47 63 48 16 1962 57 91 85 89 70 80 30 19 38 1461 35 36 20 38 18 89 64 63 88 8345 46 89 53 83 59 48 45 87 98 2115 95 24 35 79 35 55 66 91 95 86 8794 15 84 42 88 83 64 50 22 99 13 3285 12 43 39 41 23 35 97 54 98 18 8584 61 77 96 49 38 75 95 16 71 22 1418 72 97 94 43 18 59 78 33 80 68 5926 94 78 87 78 92 59 83 26 88 91 9134 84 53 98 83 49 60 11 55 17 51 7529 80 14 79 15 18 94 39 69 24 93 4166 64 88 82 21 56 16 41 57 74 51 7949 15 59 21 37 27 78 41 38 82 19 6254 91 47 29 38 67 52 92 81 99 11 2731 62 32 97 42 93 43 79 88 44 54 48

Sample Output

57268320962755

 

动规 插头DP

取一个数的要求是周围8格都不取，所以左边 左上 上 右上四个格子的状态都要判断。轮廓线上多加一格表示左上角的状态即可。

 

这是一个悲伤的故事：

　　换行时，上次的状态要整体右移一位（位运算左移），为左边留出一个空格。而在本题中，因为要判断右上角状态，所以单纯右移的话，之前状态的最右边一位如果是1，会对之后的决策造成影响。

　　因此必须将最右边的多余状态截掉（见63行）

　　而沙茶的我并不能及时发现这一点，对着看上去没什么问题的代码懵逼了一个多小时。

 

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 using namespace std; 9 const int mod=100007;10 const int mxn=100010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}15 return x*f;16 }17 int now,pre;18 struct HS{19 int v,nxt,id;20 }e[2][mxn<<3];21 int f[2][mxn<<2];22 int hd[2][mod+2],mct[2];23 void add(int v,int w){24 int z=v%mod;25 for(int i=hd[now][z];i;i=e[now][i].nxt){26 if(e[now][i].v==v){f[now][i]=max(w,f[now][i]); return;}27 }28 e[now][++mct[now]]=(HS){v,hd[now][z],z};hd[now][z]=mct[now];29 f[now][mct[now]]=w;30 return;31 }32 int n;33 int mp[17][17];34 int main(){35 // freopen("in.txt","r",stdin);36 int i,j;37 while(1){38 memset(f,-1,sizeof f);39 mct[1]=mct[0]=0;40 memset(hd,0,sizeof hd);41 char ch;42 for(n=1;n;n++){43 if(scanf("%d%c",&mp[0][n-1],&ch)==EOF)return 0;44 if(ch=='\n' || n==16)break;45 }46 for(i=1;i
           
            >(j-1))&1;//左边 73 int y=(v>>j)&1;//左上角 74 int z=(v>>(j+1))&1;//上边 75 int c=(v>>(j+2))&1;//右上角76 if( !x&& !y && !z && !c){77 add(v|(1<