题目描述:
小 A 的花园的长和宽分别是 L,H . 小 A 喜欢在花园里做游戏. 每次做游戏的时候, 他都先把花园均匀分割成 L*H 个小方块, 每个方块的长和宽都是 1 . 然后, 小 A 会从花园的西北角的小方块出发, 按照一定的规则移动, 在到达花园东南角的小方块时结束游戏. 每次行动时, 他都会移动到当前所在的小方块的东面或南面相邻的小方块上. 如果小 A 当前在从北向南数第 i 块, 从西向东数第 j 块小方块上, 他向东移动的概率是 Pij , 向南移动的概率则是 1-Pij .
在花园里做游戏常常会弄脏衣服, 花园的每个小方块内都有一定的不干净度, 用 Dij 表示. 而一次游戏结束后, 小 A 总的不干净度就是他经过的所有格子中不干净度之和(起点和终点的不干净度也计算在内).
小 B 因为小 A 经常把衣服弄脏感到苦恼, 他可能会决定在小 A 做游戏前对花园进行一次打扫. 小 B 在打扫花园时, 会从花园的西北角的小方块出发, 每次移动到当前所在的小方块的东面或南面相邻的小方块上, 在到达花园的东南角时结束打扫, 他经过的所有的格子的不干净度都会变为 0 . 现在, 小 B 想知道, 在他选择了最优的打扫策略的情况下, 小 A 做完游戏后总不干净度之和是多少?
输入格式:
第一行输入两个空格隔开的正整数 L,H.
第二行一个整数 k, 值为 0 或 1 ,k=0 表示小 B 不会打扫花园, k=1 表示小 B 会在游戏开始前打扫花园.
接下来 L 行, 每行有 H 个自然数, 第 i 行第 j 个数表示从北往南数第 i 个, 从西往东数第 j 个小方块的不干净度 Dij .
接下来 L 行, 每行有 H 个实数, 第 i 行第 j 个数表示从北往南数第 i 个, 从西往东数第 j 个小方块的参数 Pij .
输出格式:
输出一个整数, 表示问题的答案, 四舍五入保留到整数.
- INPUT
- 3 3
- 1
- 200 100 100
- 200 100 300
- 100 200 300
- 0.2 0.8 0.0
- 0.8 0.3 0.0
- 1.0 1.0 1.0
- OUTPUT
- 161
题目分析:
期望概率 \(dp\), 学这个的时候对期望概率理解得还不深刻基本没理解好吧, 所以不懂的地方很多, 可能讲得比较细
遇到期望概率 \(dp\):
- #include<bits/stdc++.h>
- #define N (1000 + 5)
- using namespace std;
- inline int read() {
- int cnt = 0, f = 1; char c = getchar();
- while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
- while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
- return cnt * f;
- }
- int l, h, k;
- double c[N][N], f[N][N], p[N][N];
- int d[N][N];
- double sum;
- signed main(){
- memset(c, 0, sizeof(c));memset(p, 0, sizeof(p));
- memset(f, 0, sizeof(f));memset(d, 0, sizeof(d));
- l = read(), h = read(), k = read();
- for (register int i = 1; i <= l; i++)
- for (register int j = 1; j <= h; j++)
- d[i][j] = read();
- for (register int i = 1; i <= l; i++)
- for (register int j = 1; j <= h; j++)
- scanf("%lf", &p[i][j]);
- sum = d[1][1];
- c[1][1] = d[1][1];
- f[1][1] = 1;
- for (register int i = 1; i <= l; i++)
- for (register int j = 1; j <= h; j++) {
- if (i == 1 && j == 1) continue;
- f[i][j] = f[i - 1][j] * (1 - p[i - 1][j]) + f[i][j - 1] * p[i][j - 1];
- c[i][j] = f[i][j] * d[i][j];
- c[i][j] += max(c[i - 1][j], c[i][j - 1]);
- sum += f[i][j] * d[i][j];
- }
- if (!k) return printf("%.0lf",sum), 0;
- printf("%.0lf", sum - c[l][h]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3123006.html