状态压缩dp（hdu2167，poj2411）

hdu2167 http://acm.hdu.edu.cn/showproblem.php?pid=2167

给定一个N*N的板子，里面有N*N个数字，选中一些数字，使得和最大

要求任意两个选中的数字不相邻，相邻包括上下，左右和对角线相邻。

由于N<=15，用程序判断了一下，每一行的有效状态<1600个,如果记录这些状态，然后每一行枚举当前行的上一行的状态那么极端下有1600*1600*15的复杂度，TLE

所以卡在这里很久，想不到怎么优化。然后看了别人的代码知道了用邻接表存储哪两个状态是相容的。这样就不用枚举那么多了。所以就过了。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <sstream>
 5 using namespace std;
 6 int matrix[15][15];
 7 int dp[1<<15][15],situation[1600],bit[15],head[1000000],e;
 8 struct node
 9 {
10     int v,next;
11 }g[1000000];;
12 int max(const int &a, const int &b)
13 {
14     return a < b ? b : a;
15 }
16 
17 void addEdge(int u, int v)
18 {
19     g[e].v = v;
20     g[e].next = head[u];
21     head[u] = e++;
22 }
23 int count(int i, int ss, int n)//计算状体第i行的状态s所取的数的和
24 {
25     int ret = 0;
26     int j = 0;
27     for(j=0; j<n; ++j)
28     {
29         if(bit[j] & ss)
30             ret += matrix[i][j];
31     }
32     return ret;
33 }
34 bool check(int s, int ss,int n)//检查s和ss是否可容
35 {
36     
37     if(s&ss) return false;
38     if((s<<1)&ss) return false;
39     if((s>>1)&ss) return false;
40     return true;
41 }
42 int main()
43 {
44     int n,i,j,m,s,ss;
45     char str[100];
46     bit[i=0] = 1;
47     for(i=1; i<15; ++i)
48         bit[i] = bit[i-1]<<1;
49     m = 1<<15;
50     for(i=0,j=0; i<m; ++i)
51         if(!(i&(i<<1)))//求出有效的状态
52             situation[j++]= i;
53     while(gets(str))
54     {
55         memset(dp,0,sizeof(dp));
56         e = 0;
57         memset(head,-1,sizeof(head));
58         n = 0;
59         do
60         {
61             j = 0;
62             stringstream scin(str);
63             while(scin>>matrix[n][j]) j++;
64             n++;
65             gets(str);
66             if(str[0]=='

状态压缩dp（hdu2167，poj2411）

相关推荐