CodeForces-295-C

题意：

　　n个人过河，只有一条船，每个人体重只有两种可能，50或者100.船最大承重 k 。船必须由某一个人来划。求最小过河需要多少趟，以及在这个次数下的方案数

解决：

　　dp[ i ][ j ][ tag ]; 对岸有 i 个体重50的人， j 个体重 100 的人，此时船在对面（若在对面 tag = 1 ）

　　bfs去搜状态。dp记录当前方案数。

  1 #include <bits/stdc++.h>
  2 
  3 long long comb[51][51];
  4 
  5 int n, k, n_50, n_100;
  6 
  7 long long dp[51][51][2];
  8 bool vis[51][51][2];
  9 
 10 const int MOD = 1e9+7;
 11 
 12 struct QueNode{
 13     int r_50, r_100;
 14     bool is_r;
 15     int step;
 16     QueNode(){}
 17     QueNode(int _r_50, int _r_100, int _is_r, int _step)
 18     {
 19         r_50 = _r_50;
 20         r_100 = _r_100;
 21         is_r = _is_r;
 22         step = _step;
 23     }
 24 };
 25 
 26 void prePro()
 27 {
 28     comb[0][0] = 1;
 29     for(int i = 1; i <= 50; ++ i){
 30         comb[i][0] = comb[i][i] = 1;
 31         for(int j = 1; j <= 50; ++ j){
 32             comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
 33         }
 34     }
 35 }
 36 
 37 int main()
 38 {
 39     prePro();
 40     std::cin >> n >> k;
 41     memset(vis, false, sizeof vis);
 42     memset(dp, 0, sizeof dp);
 43     n_50 = n_100 = 0;
 44     for(int i = 1; i <= n; ++ i){
 45         int tmp;
 46         std::cin >> tmp;
 47         if(tmp == 50){
 48             n_50 ++;
 49         }
 50         else{
 51             n_100 ++;
 52         }
 53     }
 54     dp[0][0][0] = 1;
 55     std::queue<QueNode> que;
 56     que.push(QueNode(0, 0, 0, 0));
 57     vis[0][0][0] = true;
 58     long long res = 0;
 59     int res_step = -1;
 60     while(que.empty() == false){
 61         QueNode u = que.front(), v;
 62         que.pop();
 63         //printf("dp[%d][%d][%d] = %lld
", u.r_50, u.r_100, u.is_r, dp[u.r_50][u.r_100][u.is_r]);
 64         if(u.r_50 == n_50 && u.r_100 == n_100){
 65             res_step = u.step;
 66             res = dp[n_50][n_100][1];
 67             break;
 68         }
 69         v.step = u.step + 1;
 70         if(u.is_r == true){
 71             v.is_r = false;
 72             for(int i = 0; i <= u.r_50; ++ i){
 73                 for(int j = 0; j <= u.r_100; ++ j){
 74                     if(i + j == 0)
 75                         continue;
 76                     if(i*50+j*100 > k)
 77                         continue;
 78                     long long tmp = dp[u.r_50][u.r_100][true]*comb[u.r_50][i]%MOD*comb[u.r_100][j]%MOD;
 79                     v.r_50 = u.r_50 - i;
 80                     v.r_100 = u.r_100 -j;
 81                     dp[v.r_50][v.r_100][v.is_r] += tmp;
 82                     dp[v.r_50][v.r_100][v.is_r] %= MOD;
 83                     if(vis[v.r_50][v.r_100][v.is_r] == false){
 84                         vis[v.r_50][v.r_100][v.is_r] = true;
 85                         que.push(v);
 86                     }
 87                 }
 88             }
 89         }
 90         else{
 91             v.is_r = true;
 92             for(int i = 0; i <= n_50 - u.r_50; ++ i){
 93                 for(int j = 0; j <= n_100 - u.r_100; ++ j){
 94                     if(i + j == 0)
 95                         continue;
 96                     if(i*50+j*100 > k)
 97                         continue;
 98                     long long tmp = dp[u.r_50][u.r_100][false]*comb[n_50-u.r_50][i]%MOD*comb[n_100-u.r_100][j]%MOD;
 99                     v.r_50 = u.r_50 + i;
100                     v.r_100 = u.r_100 + j;
101                     dp[v.r_50][v.r_100][v.is_r] += tmp;
102                     dp[v.r_50][v.r_100][v.is_r] %= MOD;
103                     if(vis[v.r_50][v.r_100][v.is_r] == false){
104                         vis[v.r_50][v.r_100][v.is_r] = true;
105                         que.push(v);
106                     }
107                 }
108             }
109 
110         }
111     }
112     std::cout << res_step << std::endl << res << std::endl;
113 }