本文主要是介绍hdu1565（状态压缩），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本人第一道ac的状态压缩dp，这题的数据非常水，很容易过
题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值
解题思路：
一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中
二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足cnt[k] & cnt[j] == 0,之后dp[i][j]+=sum
举个例子说明sum 的意思，比如第一行75 15 21，cnt[j] = 5，即（101），那么sum = 96
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 25
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N][N],cnt[20000],dp[25][20000];
int n,tot;void init() //求有效状态
{ tot=0; for (int i=0; i<(1<<n); i++) { if ((i<<1)&i)continue; cnt[tot++]=i; }//for(int i = 0; i < 100; i++)// cout<<cnt[i]<<" ";
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);while(scanf("%d",&n) != EOF){ init(); int i,j,k;int res = 0; for(i = 0; i < n; i++)for(j = 0; j < n; j++)scanf("%d",&a[i][j]);memset(dp,0,sizeof(dp));for(i = 0; i < tot; i++)//初始化第一行{for(j = 0; j < n; j++)if((cnt[i]&(1<<j)) > 0)dp[0][i] += a[0][j]; if(dp[0][i] > res) res = dp[0][i];}for(i = 1; i < n; i++) for(j = 0; j < tot; j++)//cnt[]记录的是有效状态 {for(k = 0; k < tot; k++)if((cnt[j]&cnt[k]) == 0) dp[i][j] = max(dp[i][j],dp[i-1][k]);for(k = 0; k < n; k++)if(((1<<k)&cnt[j]) > 0)dp[i][j] += a[i][k];if(res < dp[i][j]) res = dp[i][j]; } printf("%d\n",res); } // P; return 0;
}
这篇关于hdu1565（状态压缩）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
