hdu_5555_Immortality of Frog(状压DP)

题意：

给你一个NxN的网格，第N行的每一列都有个青蛙，这些青蛙只会往上走，上帝会在每个膜中放一个长生不老的药，一共有N个膜，每个膜覆盖一些区间，如果这个区间恰好为N那么就是好膜，否则是坏膜，每个青蛙最多只能穿过10个坏膜，问全部青蛙吃到药，并全部到顶层的分配方案。

题解：

1.我们首先统计每一列有多少个坏膜，其中一列如果大于10，那么青蛙肯定不能全部到达顶部，ans=0;

2.假设青蛙把全部的坏膜吃完了，当前的方案数为p，好膜是都可以吃的，那么此时的答案就是好膜的个数的阶乘*p。

3.这时我们就该来算全部吃完坏膜的方案数了。

4.首先每一列最多只有10个坏膜，那么我们可以用状态压缩来保存每一列坏膜的状态，但这个状态只是这一列的相对位置,比如这一列第10行的坏膜的相对位置为1，第24行的坏膜相对位置为2

5.我们dp[i][j]表示第i列的坏膜相对位置的吃掉情况，那么我们要转移到i+1列，就要转移第i列已经吃过的坏膜的情况到第i+1列，因为j表示的是当前列的坏膜相对位置，我们要对应找到i+1列的坏膜的相对位置，列如：第i列有第12，15，18，20是坏膜，第i+1列有第15，20，30，40是坏膜，假设第i列的第15行坏膜已经吃掉，第15行在第i列的相对位置为2，此时我们要转移到i+1列上，对应的就是第i+1列的15行，第15行在i+1列的相对位置为1，这样就是dp[i][1<<(2-1)]转移到了dp[i+1][1<<(1-1)]。

6.到最后我们取的是最后一列的全部坏膜吃掉的情况，这里就包含了所有坏膜吃完的情况，然后乘上好膜的阶乘即可

 1 #include<cstdio>
 2 #include<vector>
 3 #define F(i,a,b) for(int i=a;i<=b;i++)
 4 typedef long long LL;
 5 using namespace std;
 6 
 7 const int N=1030,mod=105225319;
 8 int dp[N][N],n,l[N],r[N],good,jie[N],p1[20],p2[20];
 9 vector<int>g[N];
10 
11 void init(){
12     jie[0]=1;
13     F(i,1,1000)jie[i]=(LL)jie[i-1]*i%mod;
14 }
15 
16 void del(int x){
17     F(i,0,(int)g[x].size()-1){
18         p1[i]=-1;
19         F(j,0,(int)g[x+1].size()-1)
20             if(g[x][i]==g[x+1][j]){p1[i]=j;break;}
21     }
22     F(i,0,(int)g[x+1].size()-1){
23         p2[i]=-1;
24         F(j,0,(int)g[x].size()-1)
25             if(g[x+1][i]==g[x][j]){p2[i]=j;break;}
26     }
27 }
28 
29 inline int new_s(int x,int y){
30     int ans=0;
31     F(i,0,(int)g[x].size()-1){
32         if(p1[i]==-1){if(!((y>>i)&1))return -1;}
33         else if(y>>i&1)ans|=(1<<p1[i]);
34     }//这个坏膜在当前列的编号对应下一列的编号
35     return ans;
36 }
37 
38 inline void up(int &x,int y){x+=y,x=x>mod?x-mod:x;}
39 
40 int main(){
41     init();
42     int t;scanf("%d",&t);
43     F(ic,1,t){
44         scanf("%d",&n),good=0;
45         F(i,1,n)scanf("%d",l+i),g[i].clear();
46         F(i,1,n)scanf("%d",r+i);
47         F(i,1,n)if(l[i]==1&&r[i]==n)good++;
48         else F(j,l[i],r[i])g[j].push_back(i);
49         int flag=0,ans=0;//坏膜大于10,无法分配
50         F(i,1,n)if(g[i].size()>10){flag=1;break;}
51         if(!flag){
52             F(i,1,n){//dp初始化
53                 int sz=g[i].size();
54                 F(j,0,(1<<sz))dp[i][j]=0;
55             }
56             dp[0][0]=1;
57             F(i,0,n-1){
58                 del(i);
59                 F(j,0,(1<<(int)g[i].size())-1){
60                     int now=new_s(i,j);
61                     if(now!=-1){//将上一列已经吃过的坏膜转移到这列对应的状态
62                         up(dp[i+1][now],dp[i][j]);
63                         F(k,0,(int)g[i+1].size()-1)//如果上一列没有这个坏膜或者有但没吃，那么这一列肯定吃掉这个膜
64                             if(p2[k]==-1||!(now>>k&1))
65                             up(dp[i+1][now|(1<<k)],dp[i][j]);
66                     }
67                 }
68             }
69         ans=(LL)jie[good]*dp[n][(1<<(int)g[n].size())-1]%mod;
70         }
71         printf("Case #%d: %d
",ic,ans);
72     }
73     return 0;
74 }

View Code