hdu 1565 方格取数(1) 状压DP
来源：程序员人生 发布时间：2015-06-01 08:48:36 阅读次数：2307次
方格取数(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
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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
