本文主要是介绍HDU1565方格取数（1）（状态压缩DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5530 Accepted Submission(s): 2094
Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的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
解题：DP[i][j],表示前i行，第i行为第j状态,的最大取数和。
#include<stdio.h>
#include<string.h>
#define mulit(i) (1<<(i))
#define ll int
#define N 16
ll dp[N][mulit(N)+1],sta[N][mulit(N)],sum[N][mulit(N)],sk[N],map[N][N];
void init(int n)
{for(int i=0;i<n;i++){sk[i]=0;for(int j=0;j<mulit(n);j++){int e; sum[i][sk[i]]=0;for(e=0;mulit(e)<=j;e++)if(mulit(e)&j){sum[i][sk[i]]+=map[i][e];if((mulit(e-1)&j)&&e>0)break;}if(mulit(e)>j){//printf("%I64d ",sta[i][sk[i]]);sta[i][sk[i]]=j; sk[i]++;}//}}
}
void count(int n)
{memset(dp,0,sizeof(dp));for(ll i=0;i<sk[0];i++)dp[0][i]=sum[0][i];for(ll i=1;i<n;i++)for(ll j=0;j<sk[i];j++)for(ll tj=0;tj<sk[i-1];tj++)if((sta[i][j]&sta[i-1][tj])==0)//==优先级大于&if(dp[i][j]<dp[i-1][tj]+sum[i][j])dp[i][j]=dp[i-1][tj]+sum[i][j];
}
int main()
{int n;while(scanf("%d",&n)>0){for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&map[i][j]);init(n);count(n);ll max=0;for(ll i=0;i<sk[n-1];i++)if(dp[n-1][i]>max)max=dp[n-1][i];printf("%d\n",max);}
}
这篇关于HDU1565方格取数（1）（状态压缩DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
