思路出来有点有意思：是树型加状压的转移。
将分部压掉就可以了
但我是挂在了初始化上……
(QAQ)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=101;
int n,m,t;
int val[4100],cost[101][20];
int head[4*N],num_edge,dp[401][4100];
struct Edge{int next,to;} edge[4*N];
inline void add(int from,int to)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
head[from]=num_edge;
}
inline void dfs(int pos,int fa)
{
for(int i=head[pos];i;i=edge[i].next)
if(edge[i].to!=fa)
{
dfs(edge[i].to,pos);
for(int j=(1<<m)-1;j;j--)
for(int k=j;k;k=(k-1)&j)
dp[pos][j]=max(dp[pos][j],dp[pos][j^k]+dp[edge[i].to][k]);
}
for(int i=(1<<m)-1;i;i--) dp[pos][i]+=val[i];
}
int main(){
n=read(),m=read();
//memset(head,-1,sizeof(head)),num_edge=-1;
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
cost[i][j]=read();
dp[i][0]=0;
for(int j=1;j<(1<<m);j++)
{
int lowbit=j&(-j),lownum=(log(lowbit)+0.0001)/(log(2));
dp[i][j]=dp[i][j^lowbit]-cost[i][lownum];
}
}
t=read();
for(int i=1;i<=t;i++)
{
int v=read(),cnt=read(),s=0;
for(int j=1;j<=cnt;j++)
{
int part=read();
s|=(1<<(part-1));
}
val[s]+=v;
int tot=(1<<m)-1,tmp=s^tot;
for(int j=tmp;j;j=(j-1)&tmp) val[(s|j)]+=v;
}
dfs(1,0);
printf("%d",dp[1][(1<<m)-1]);
}
现在才发现，状压(DP)的状态很考思维，即你的状态和你的转移有很大关系。
如果，你的状态压的好，就会很简化方程，相反如果你的状态一般，很有可能不太好转移甚至是无法转移！
这一题的状态很有意思，其实一开始我想的是横着放的标为(0),竖着放的标为(1)。
但是有一个极为明显的问题：
像这样的状态，就会有无法判定当前行和上一行的关系，状态不能对应（相当于是无法判定竖着放的是否残缺）
因此就有这样的状态，很有意思：横着放的为(1),而竖着放的上(0)下(1),这样就很巧妙的避免了上面的问题。
相当于我们用(1)来判定了当前位置是否为一个结束。
那么转移就很好办了，状压的转移一般只要手玩一下就可以了吧（也许是我还没做到这样的毒瘤题？(QwQ)）
嘿呀，上代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>//忍不住要吐槽poj的头文件，真的恶心哈
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
int n,m;
long long f[15][1<<12];
inline bool FirLin(int s)
{
for(int i=0;i<m;)
if(s&(1<<i))
{
if(i==m-1) return 0;
if(s&(1<<i+1)) i+=2;
else return 0;
}
else i++;
return 1;
}
inline bool judge(int now,int pre)
{
for(int i=0;i<m;)
if(now&(1<<i))
if(pre&(1<<i))
if(i!=m-1&&(now&(1<<i+1))&&(pre&(1<<i+1))) i+=2;
else return 0;
else i++;
else if(pre&(1<<i)) i++;
else return 0;
return 1;
}
int main(){
while(scanf("%d%d",&n,&m)&&n&&m)
{
if(n<m) swap(n,m);
memset(f,0,sizeof(f));
for(int i=0;i<(1<<m);i++) f[1][i]=FirLin(i)?1:0;
for(int i=2;i<=n;i++)
for(int j=0;j<(1<<m);j++)
for(int k=0;k<(1<<m);k++)
if(judge(j,k)) f[i][j]+=f[i-1][k];
printf("%lld
",f[n][(1<<m)-1]);
}
}
下一个：一个三进制的状压(DP)，说实话，我以前的思维被二进制的状压禁锢，应该说没有考虑过其他进制。
观察可得，显然当前行的状态与前两行的状态有关系，不妨将前两行压在一起，用一个三进制表示，具体的压法为：
(0)表示(i)和(i-1)行都没有放;(1)表示(i)行没放(i-1)行放了;(2)表示(i)和(i-1)行都放了
转移时分个类，讨个论即可：
上代码了呦！
//0表示i和i-1行都没有放//1表示i行没放i-1行放了//2表示i和i-1行都放了
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>//忍不住要吐槽poj的头文件，真的恶心哈
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
int n,m,k,las,now,c;
int a[200][30],pw[20],f[2][60000];
inline int Las(int i) {return las/pw[i-1]%3;}
inline int Now(int i) {return now/pw[i-1]%3;}
inline void Dfs(int Lin,int cnt)//在基础状态上跑出所有可能的放法
{
if(Lin>m) return ;
if(Lin<m&&!Las(Lin)&&!Las(Lin+1)&&!Now(Lin)&&!Now(Lin+1))
{
now+=(pw[Lin-1]+pw[Lin])*2;f[c][now]=max(f[c][now],cnt+1);
Dfs(Lin+2,cnt+1),now-=(pw[Lin-1]+pw[Lin])*2;
}
if(Lin<m-1&&!Now(Lin)&&!Now(Lin+1)&&!Now(Lin+2))
{
now+=(pw[Lin-1]+pw[Lin]+pw[Lin+1])*2;f[c][now]=max(f[c][now],cnt+1);
Dfs(Lin+3,cnt+1),now-=(pw[Lin-1]+pw[Lin]+pw[Lin+1])*2;
}
Dfs(Lin+1,cnt);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Text1.in","r",stdin);
#endif
int t=read();pw[0]=1;
for(int i=1;i<11;i++) pw[i]=pw[i-1]*3;
while(t--)
{
n=read(),m=read(),k=read(),las=0;
memset(a,0,sizeof(a));
memset(f[0],-1,sizeof(f[0]));
for(int i=1,u,v;i<=k;i++) u=read(),v=read(),a[u][v]=1;
for(int i=1;i<=m;i++) las+=pw[i-1]*(a[1][i]+1);
f[0][las]=0,c=0;int ans=0;
for(int i=2;i<=n;i++)
{
c^=1;
memset(f[c],-1,sizeof(f[c]));
for(las=0;las<pw[m];las++)
if(~f[c^1][las])
{
now=0;
for(int j=1;j<=m;j++)
if(a[i][j]) now+=pw[j-1]*2;
else now+=pw[j-1]*(Las(j)?Las(j)-1:0);//跑出对应基础状态（即啥也不放的必须状态）
f[c][now]=max(f[c][now],f[c^1][las]),Dfs(1,f[c^1][las]);
}
}
for(int i=0;i<pw[m];i++) ans=max(ans,f[c][i]);
printf("%d
",ans);
}
}