花园【SCOI2017期望DP入门题】

花园【SCOI2017期望DP入门题】
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说花园【SCOI2017期望DP入门题】,希望能够帮助大家进步!!!

题目描述:

小 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\)
IMG_20190714_005333.png
(来自\(linners\)
首先我们很明显可以想到的是,每个节点的状态是可以从它左边和上面转移过来的。想到这一点,状态转移方程就好设计了。
容易有\(f[i][j] = f[i - 1][j] * (1 - p[i - 1][j]) + f[i][j - 1] * p[i][j - 1]\),然后这个\(f\)数组处理出来的是概率,每次把不干净值乘上去再累加到\(ans\)上并一直递推下去
然后发现,如果没有小\(B\)这个人的话,其实我们的问题就已经搞定了所以为什么小B这么事儿多,直接输出
如果有的话,考虑在期望图上再做一次\(dp\)记录转移过来的当前最长链并累加起来,最后在答案上减去即可
这里说一下为什么要在期望图上做\(dp\)而非在原不干净值的图上做\(dp\)(对这个理解不深刻,卡的很久):
如果在原图上做\(dp\),相当于忽略了期望带来的影响。形象地讲,假设我们打扫了一个很脏很脏的格子,然后这个人有百万分之一的概率去踩这个格子
……那我可打扫个毛线啊!不如打扫一个相对比较脏,踩的几率更大的格子
而期望的本质是每种事件发生对答案贡献的加权平均,在期望图(即贡献的加权平均图上)跑一遍\(dp\)找出小\(B\)清理的最优策略,这个最优策略本质上是对答案影响最大(减少最多)的贡献的加权平均,不然数学意义都不一样怎么相减呢。

代码:

#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;
}

转载于:https://www.cnblogs.com/kma093/p/11182872.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29668

发表评论