方格取数(1)Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6096Accepted Submission(s): 2331
Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input
包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例，输出可能取得的最大的和
Sample Input
375 15 21 75 15 28 34 70 5
Sample Output
188
Author
ailyanlu
链接：?pid=1565
两个11不相零的二十位 二进制一共有17000个，这题数据比较水，循环两次 居然没超时。
做法：dp[cur][j],cur滚动数组，j表示第j个 符合要求的 二进制数。dp[cur][j]为当前行，j状态 和的最大值。然后不断加，然后上下行不排除的转移下来就可以了。
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#include <malloc.h>#include <ctype.h>#include <math.h>#include <string>#include <iostream>#include <algorithm>using namespace std;#include <stack>#include <queue>#include <vector>#include <deque>#include <set>#include <map>#define INF 999999999#define eps 0.00001#define LL __int64d#define pi acos(-1.0)vector <int >my;map<int ,int>mp;int dp[2][17711];int n;int ok(int num){ if(num&(num>>1))return 0;return 1;}int num[20][20];int main(){ for(int i=0;i<(1<<20);i++){if(ok(i)){my.push_back(i);mp[i]=mp.size();}}//printf("%d %d\n",my.size(),(1<<20));while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&num[i][j]);}}memset(dp,0,sizeof dp);int cur=0;for(int i=0;i<n;i++){cur^=1;memset(dp[cur],0,sizeof dp[cur]);for(int j=0;my[j]<(1<<n);j++){int tem=0;for(int k=0;k<n;k++){if(my[j]&(1<<k)){tem+=num[i][k];}}for(int k=0;my[k]<(1<<n);k++){if((my[j]&my[k])==0)dp[cur][j]=max(dp[cur^1][k]+tem,dp[cur][j]);}}} int maxx=0;for(int j=0;my[j]<(1<<n);j++){maxx=max(maxx,dp[cur][j]);}printf("%d\n",maxx);}return 0;}
回味起来却有久久不会退去的余香。
