客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
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 n, k (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 }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论