• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces295CGregandFriends(BFS+DP)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

One day Greg and his friends were walking in the forest. Overall there were n people walking, including Greg. Soon he found himself in front of a river. The guys immediately decided to get across the river. Luckily, there was a boat by the river bank, just where the guys were standing. We know that the boat can hold people with the total weight of at most k kilograms.

Greg immediately took a piece of paper and listed there the weights of all people in his group (including himself). It turned out that each person weights either 50 or 100 kilograms. Now Greg wants to know what minimum number of times the boat needs to cross the river to transport the whole group to the other bank. The boat needs at least one person to navigate it from one bank to the other. As the boat crosses the river, it can have any non-zero number of passengers as long as their total weight doesn't exceed k.

Also Greg is wondering, how many ways there are to transport everybody to the other side in the minimum number of boat rides. Two ways are considered distinct if during some ride they have distinct sets of people on the boat.

Help Greg with this problem.

 

Input

The first line contains two integers nk (1 ≤ n ≤ 50, 1 ≤ k ≤ 5000) — the number of people, including Greg, and the boat's weight limit. The next line contains n integers — the people's weights. A person's weight is either 50 kilos or 100 kilos.

You can consider Greg and his friends indexed in some way.

Output

In the first line print an integer — the minimum number of rides. If transporting everyone to the other bank is impossible, print an integer-1.

In the second line print the remainder after dividing the number of ways to transport the people in the minimum number of rides by number 1000000007 (109 + 7). If transporting everyone to the other bank is impossible, print integer 0.

 

题目大意:n个人,有人的体重是50,有的人体重是100,船只只能承受k的重量。现在只有一条船,问最少须要渡河多少次,才能把这n个人都送到对岸(渡河时船上不能没人),在最小次数下问有多少种方案渡河,同一体重的两个人视为不同的人。

思路:设dis[x][y][boat]代表原来的岸上有x个体重为50的人,y个体重为100的人,有一条船在原来的岸上(其实boat不是0就是1),到结束状态dis[0][0][0]的最短距离。从状态dis[0][0][0]开始做最短路,每一步代价为1,故使用BFS,转移的时候只需要注意船上至少有一个人,重量不要超过k就好了。

那么dis[][][]数组求好了,从起始状态dis[n1][n2][1]到最终状态的最少渡河次数就能求出来了,其中n1代表原来有n1个体重为50的人,n2为原来用n2个体重为100的人。

然后求次数,dp就可以了。状态类似用dp[x][y][boat]表示到达某个状态的方案,对于下一个方案dp[i][j][!boat],当且仅当dis[i][j][!boat] + 1 = dis[x][y][boat],船不为空,不超载时转移。

dp[i][j][!boat] += dp[x][y][boat] * (可以移动的体重为50的人选需要移动的体重为50的人的方案数) * (可以移动的体重为100的人选需要移动的体重为100的人的方案数)

复杂度为O(n^4)

不过实际上可以在求dis的时候直接倒着把dp也算了……

 

代码(30MS):

  1 #include <cstring>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <queue>
  6 using namespace std;
  7 typedef long long LL;
  8 typedef pair<int, int> PII;
  9 
 10 const int MAXN = 55;
 11 const int INF = 0x3f3f3f3f;
 12 const int MOD = 1000000007;
 13 
 14 struct State {
 15     int x, y, boat;
 16     State() {}
 17     State(int x, int y, int boat):
 18         x(x), y(y), boat(boat) {}
 19 };
 20 
 21 int dis[MAXN][MAXN][2], vis[MAXN][MAXN][2];
 22 LL dp[MAXN][MAXN][2], c[MAXN][MAXN];
 23 int n, k, n1, n2;
 24 
 25 void init() {
 26     c[0][0] = 1;
 27     for(int i = 1; i <= 50; ++i) {
 28         c[i][0] = 1;
 29         for(int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
 30     }
 31     //int a, b; while(cin>>a>>b) cout<<c[a][b]<<endl;
 32 }
 33 
 34 void bfs() {
 35     memset(dis, 0x3f, sizeof(dis));
 36     queue<State> que; que.push(State(0, 0, 0));
 37     dis[0][0][0] = 0;
 38     while(!que.empty()) {
 39         State p = que.front(); que.pop();
 40         if(p.boat == 0)
 41             for(int i = p.x; i <= n1; ++i)
 42                 for(int j = p.y; j <= n2; ++j) {
 43                     if(i == p.x && j == p.y) continue;
 44                     if(dis[i][j][1] != INF || (i - p.x) + 2 * (j - p.y) > k) continue;
 45                     dis[i][j][1] = dis[p.x][p.y][0] + 1;
 46                     que.push(State(i, j, 1));
 47                 }
 48         else
 49             for(int i = 0; i <= p.x; ++i)
 50                 for(int j = 0; j <= p.y; ++j) {
 51                     if(i == p.x && j == p.y) continue;
 52                     if(dis[i][j][0] != INF || (p.x - i) + 2 * (p.y - j) > k) continue;
 53                     dis[i][j][0] = dis[p.x][p.y][1] + 1;
 54                     que.push(State(i, j, 0));
 55                 }
 56     }
 57 }
 58 
 59 LL solve() {
 60     if(dis[n1][n2][1] == INF) {
 61         puts("-1");
 62         return 0;
 63     }
 64     queue<State> que; que.push(State(n1, n2, 1));
 65     dp[n1][n2][1] = 1;
 66     while(!que.empty()) {
 67         State p = que.front(); que.pop();
 68         if(p.boat == 1)
 69             for(int i = 0; i <= p.x; ++i)
 70                 for(int j = 0; j <= p.y; ++j) {
 71                     if(i == p.x && j == p.y) continue;
 72                     if((p.x - i) + 2 * (p.y - j) > k) continue;
 73                     if(dis[i][j][0] + 1 != dis[p.x][p.y][1]) continue;
 74                     dp[i][j][0] = (dp[i][j][0] + dp[p.x][p.y][1] * (c[p.x][p.x - i] * c[p.y][p.y - j]) % MOD) % MOD;
 75                     if(!vis[i][j][0]) {
 76                         vis[i][j][0] = true;
 77                         que.push(State(i, j, 0));
 78                     }
 79                 }
 80         else
 81             for(int i = p.x; i <= n1; ++i)
 82                 for(int j = p.y; j <= n2; ++j) {
 83                     if(i == p.x && j == p.y) continue;
 84                     if((i - p.x) + 2 * (j - p.y) > k) continue;
 85                     if(dis[i][j][1] + 1 != dis[p.x][p.y][0]) continue;
 86                     dp[i][j][1] = (dp[i][j][1] + dp[p.x][p.y][0] * (c[n1 - p.x][i - p.x] * c[n2 - p.y][j - p.y]) % MOD) % MOD;
 87                     if(!vis[i][j][1]) {
 88                         vis[i][j][1] = true;
 89                         que.push(State(i, j, 1));
 90                     }
 91                 }
 92     }
 93     cout<<dis[n1][n2][1]<<endl;
 94     return dp[0][0][0];
 95 }
 96 
 97 int main() {
 98     init();
 99     scanf("%d%d", &n, &k);
100     k /= 50;
101     for(int i = 1; i <= n; ++i) {
102         int x;
103         scanf("%d", &x);
104         n1 += (x == 50);
105     }
106     n2 = n - n1;
107     bfs();
108     cout<<solve()<<endl;
109 }
View Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#中引用(ref关键字)参数发布时间:2022-07-13
下一篇:
分治法求解最近对问题(c++)发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap