hdu 1565 方格取數(1) 狀壓DP

方格取數(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 給你一個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  

連結：http://acm.hdu.edu.cn/showproblem.php?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;
}