方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5530 Accepted Submission(s): 2094
Problem Description 给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input 包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output 对于每个测试实例，输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
Author ailyanlu 解题：DP[i][j],表示前i行，第i行为第j状态,的最大取数和。
#include
#include
#define mulit(i) (1<<(i)) #define ll int #define N 16 ll dp[N][mulit(N)+1],sta[N][mulit(N)],sum[N][mulit(N)],sk[N],map[N][N]; void init(int n) { for(int i=0;i
0)break; } if(mulit(e)>j) {//printf("%I64d ",sta[i][sk[i]]); sta[i][sk[i]]=j; sk[i]++; }// } } } void count(int n) { memset(dp,0,sizeof(dp)); for(ll i=0;i
0) { for(int i=0;i
max) max=dp[n-1][i]; printf("%d\n",max); } }