hdu 1565 方格取數(1) 狀壓DP
來源：程序員人生 發布時間：2015-06-01 08:48:36 閱讀次數：2515次
方格取數(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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
