程序员人生 网站导航

hdu 1565 方格取数(1) 状压DP

栏目:综合技术时间:2015-06-01 08:48:36

方格取数(1)

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6096    Accepted Submission(s): 2331


Problem Description
给你1个n*n的格子的棋盘,每一个格子里面有1个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
 

Input
包括多个测试实例,每一个测试实例包括1个整数n 和n*n个非负数(n<=20)
 

Output
对每一个测试实例,输出可能获得的最大的和
 

Sample Input
3 75 15 21 75 15 28 34 70 5
 

Sample Output
188
 

Author
ailyanlu
 

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1565



两个11不相零的210位 2进制1共有17000个,这题数据比较水,循环两次 竟然没超时。

做法:dp[cur][j],cur转动数组,j表示第j个 符合要求的 2进制数。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(⑴.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 ",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 ",maxx); } return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐