方格取数(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个格子不能相邻,并且取出的数的和最大。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的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<stdio.h> #include<string.h> #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<n;i++) { sk[i]=0; for(int j=0;j<mulit(n);j++) { int e; sum[i][sk[i]]=0; for(e=0;mulit(e)<=j;e++) if(mulit(e)&j) { sum[i][sk[i]]+=map[i][e]; if((mulit(e-1)&j)&&e>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<sk[0];i++) dp[0][i]=sum[0][i]; for(ll i=1;i<n;i++) for(ll j=0;j<sk[i];j++) for(ll tj=0;tj<sk[i-1];tj++) if((sta[i][j]&sta[i-1][tj])==0)//==优先级大于& if(dp[i][j]<dp[i-1][tj]+sum[i][j]) dp[i][j]=dp[i-1][tj]+sum[i][j]; } int main() { int n; while(scanf("%d",&n)>0) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&map[i][j]); init(n); count(n); ll max=0; for(ll i=0;i<sk[n-1];i++) if(dp[n-1][i]>max) max=dp[n-1][i]; printf("%d\n",max); } }