【HDOJ5555】Immortality of Frog（状压DP）

题意：给你一个NxN的网格，第N行的每一列都有个青蛙，这些青蛙只会往上走，

上帝会在每个膜中随机等概率放一个长生不老的药，

一共有N个膜，每个膜覆盖一些区间，如果这个区间恰好为N那么就是好膜，否则是坏膜，每个青蛙最多只能穿过10个坏膜，

问全部青蛙吃到药，并全部到顶层的概率*∏Ni=1(Ri−Li+1)

n<=1e3，1<=l[i]<=r[i]<=n

思路：经过思考可以发现其实就是让你求每只蛙都有且仅有配对到一个膜的方案数

From https://blog.csdn.net/bin_gege/article/details/51889815

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

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

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

4.首先每一列最多只有10个坏膜，那么我们可以用状态压缩来保存每一列坏膜的状态，记录每一列坏膜的相对位置，对于每一次转移处理出对于新的一行的状态

第一次用vector，需要注意vector从0开始编号，当vector为空时因为size是一个unsigned int，-1会出现越界的问题，所以每次都需要强制类型转换成int

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<vector>
  6  
  7 typedef long long ll;
  8 using namespace std;
  9 #define N   1100 
 10 #define oo  10000000
 11 #define MOD 105225319
 12 
 13 int dp[N][N],l[N],r[N],fac[N],p1[N],p2[N],n;
 14 vector<int>c[N];
 15 
 16 void add(int &x,int y)
 17 {
 18     x+=y;
 19     if(x>=MOD) x-=MOD;
 20 }
 21 
 22 void calc(int k)
 23 {
 24     for(int i=0;i<=(int)c[k].size()-1;i++)
 25     {
 26         p1[i]=-1;
 27         for(int j=0;j<=(int)c[k+1].size()-1;j++)
 28          if(c[k][i]==c[k+1][j]){p1[i]=j; break;}
 29     }
 30     for(int i=0;i<=(int)c[k+1].size()-1;i++)
 31     {
 32         p2[i]=-1;
 33         for(int j=0;j<=(int)c[k].size()-1;j++)
 34          if(c[k+1][i]==c[k][j]){p2[i]=j; break;}
 35     }
 36 }
 37 
 38 int turn(int x,int y)
 39 {
 40     int t=0;
 41     for(int i=0;i<=(int)c[x].size()-1;i++)
 42     {
 43         if(p1[i]==-1)
 44         {
 45             if(!((y>>i)&1)) return -1;
 46         }
 47          else if(y>>i&1) t|=(1<<p1[i]);
 48     }
 49     return t;
 50 }
 51 
 52 int main()
 53 { 
 54      fac[0]=1;
 55     for(int i=1;i<N;i++) fac[i]=(ll)fac[i-1]*i%MOD; 
 56     int cas; 
 57     scanf("%d",&cas);
 58     for(int v=1;v<=cas;v++)
 59     {
 60         scanf("%d",&n);
 61         for(int i=1;i<=n;i++) c[i].clear();
 62         for(int i=1;i<=n;i++) scanf("%d",&l[i]);
 63         for(int i=1;i<=n;i++) scanf("%d",&r[i]);
 64         int num=0;
 65         for(int i=1;i<=n;i++)
 66         {
 67             if(l[i]==1&&r[i]==n) num++;
 68              else 
 69               for(int j=l[i];j<=r[i];j++) c[j].push_back(i);
 70         }
 71         
 72         int flag=1,ans=0;
 73         for(int i=1;i<=n;i++) 
 74          if(c[i].size()>10){flag=0; break;}
 75         if(flag)
 76         {
 77             for(int i=1;i<=n;i++)
 78              for(int j=0;j<=(1<<(int)c[i].size());j++) dp[i][j]=0;
 79             dp[0][0]=1;
 80             for(int i=0;i<=n-1;i++)
 81             { 
 82                 calc(i);
 83                 for(int j=0;j<=(1<<(int)c[i].size())-1;j++)
 84                 {
 85                     int t=turn(i,j);
 86                     if(t!=-1)
 87                     {
 88                         //坏膜的数量可能比蛙少，所以可能会出现当前蛙不需要走坏膜的情况
 89                         add(dp[i+1][t],dp[i][j]);     
 90                         for(int k=0;k<=(int)c[i+1].size()-1;k++)
 91                          if(p2[k]==-1||!(t>>k&1)) add(dp[i+1][t|(1<<k)],dp[i][j]);
 92                     }        
 93                 }
 94             }
 95             ans=(ll)fac[num]*dp[n][(1<<(int)c[n].size())-1]%MOD;
 96         } 
 97         printf("Case #%d: %d
",v,ans);
 98     }
 99     return 0;
100 }
101