hdu2167 http://acm.hdu.edu.cn/showproblem.php?pid=2167
给定一个N*N的板子，里面有N*N个数字，选中一些数字，使得和最大
要求任意两个选中的数字不相邻，相邻包括上下，左右和对角线相邻。
由于N<=15，用程序判断了一下，每一行的有效状态<1600个,如果记录这些状态，然后每一行枚举当前行的上一行的状态那么极端下有1600*1600*15的复杂度，TLE
所以卡在这里很久，想不到怎么优化。 然后看了别人的代码知道了用邻接表存储哪两个状态是相容的。这样就不用枚举那么多了。所以就过了。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int matrix[][];
int dp[<<][],situation[],bit[],head[],e;
struct node
{
int v,next;
}g[];;
int max(const int &a, const int &b)
{
return a < b ? b : a;
} void addEdge(int u, int v)
{
g[e].v = v;
g[e].next = head[u];
head[u] = e++;
}
int count(int i, int ss, int n)//计算状体第i行的状态s所取的数的和
{
int ret = ;
int j = ;
for(j=; j<n; ++j)
{
if(bit[j] & ss)
ret += matrix[i][j];
}
return ret;
}
bool check(int s, int ss,int n)//检查s和ss是否可容
{ if(s&ss) return false;
if((s<<)&ss) return false;
if((s>>)&ss) return false;
return true;
}
int main()
{
int n,i,j,m,s,ss;
char str[];
bit[i=] = ;
for(i=; i<; ++i)
bit[i] = bit[i-]<<;
m = <<;
for(i=,j=; i<m; ++i)
if(!(i&(i<<)))//求出有效的状态
situation[j++]= i;
while(gets(str))
{
memset(dp,,sizeof(dp));
e = ;
memset(head,-,sizeof(head));
n = ;
do
{
j = ;
stringstream scin(str);
while(scin>>matrix[n][j]) j++;
n++;
gets(str);
if(str[]=='\0') break; }while(true);
m = <<n;
for(i=;situation[i]<m; ++i)//判断哪两个状体相容，然后用邻接表存储
for(j=; situation[j]<m; ++j)
if(check(situation[i],situation[j],n))
addEdge(i,j);
for(i=; situation[i]<m; ++i)
dp[situation[i]][] = count(,situation[i],n);
for(i=; i<n; ++i)
for(s=;situation[s]<m; ++s)
{
for(j=head[s];j!=-;j=g[j].next)
{
dp[situation[g[j].v]][i] = max(dp[situation[g[j].v]][i],dp[situation[s]][i-]+count(i,situation[g[j].v],n));
}
}
int ans = ;
for(i=; situation[i]<m; ++i)
{
ans = max(ans,dp[situation[i]][n-]);
}
printf("%d\n",ans);
}
return ;
}
poj2411 http://poj.org/problem?id=2411
给定一个N*M的矩形，用1*2的矩阵填充满，问有多少种填充的方法。 N,M<=11
状态压缩dp，时间复杂度是N*(1<<M)*(1<<M),可以使用邻接表存储，哪些状态是相容的，这样子，就不用枚举所有的状态了。
状态是如何转移的呢?
首先第一行的状态必须是：如果有1，那么必须有连续的两个1.即不能有单独的一个1.
这样子是为了，第二行如果竖着放，那么就可以填充第一行的空缺。
怎么判断当前行的状态和上一行的状态不冲突的？详见bool check(int s, int ss)函数注释
#include <stdio.h>
#include <string.h>
#define LL __int64
int n,m;
int e,head[];
LL dp[<<][];
struct node
{
int v,next;
}g[]; void addEdge(int a, int b)
{
g[e].v = b;
g[e].next = head[a];
head[a] = e++;
}
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
bool check(int s)
{
while(s)
{
if( (s&) && ((s>>)&))
s>>=;
else if( (s&) && !((s>>)&))
return false;
else if(!(s&))
s>>=; }
return true;
}
bool check(int s, int ss)
{
for(int i=; i<m; ++i)
{
if(!(s&) && !(ss&)) return false;//上一行该位置为0，那么这一行该位置应该竖着放,否则不相容
else if(!(s&)&&(ss&))
{
s>>=;ss>>=;continue;//上一行为0，这一行竖着放
}
else if((s&)&&!(ss&))
{
s>>=;ss>>=;continue;//上一行该位置为1，这一行可以不放
}
else if((s&)&&(ss&))//上一行的该位置和这一行的该位置为1，那么这行的矩形是横着放
{
s>>=,ss>>=;i++;
if((s&)&&(ss&)) //即下一个位置，上一行和这一行都必须为1
{
s>>=;ss>>=;continue;
}
else return false;
}
}
return true;
}
int main()
{
int s,ss,t,i,j;
LL ans;
while(scanf("%d%d",&n,&m),n)
{
memset(dp,,sizeof(dp));
if(n<m) swap(n,m);
ans = ;
t = <<m;
memset(head,-,sizeof(head));
e = ;
for(s=; s<t; ++s)
for(ss=; ss<t; ++ss)
if(check(s,ss))
addEdge(s,ss);
if((n*m)%==)
{
for(s=; s<t; ++s)
if(check(s))
dp[s][] = ;
for(i=; i<n; ++i)
for(s=; s<t; ++s)
for(j=head[s];j!=- && g[j].v<t;j=g[j].next)
dp[g[j].v][i] += dp[s][i-]; ans = dp[(<<m)-][n-];
}
printf("%I64d\n",ans);
}
return ;
}