花园【SCOI2017期望DP入门题】

题目

题目背景
SCOI2017 DAY2 T1
题目描述
小 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 。
输出格式
输出一个整数，表示问题的答案，四舍五入保留到整数。
样例数据
输入
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
输出
161
备注
【数据范围】
你的答案必须和标准输出完全一致才能得分，为确保精度误差在一定范围内的答案能被接受，
保证准确答案的小数点后第 1 位数字不是 4 或 5 。
0≤Dij≤10000 ；
0≤Pij≤1 最多包含两位小数 ；
PLi=1 (1≤i＜H) 且 PiH=0 (1≤i＜L)，即走到棋盘外的概率为 0 ，最终必然会到达东南角结束。PLH=1，但到达这里时旅途已经结束了，这个数没有意义；
1≤L,H≤3000 。

很好做的一道题，每个点可以由它上面的那个点和左边的点相加而来

dp[i][j]表示走到点（i，j）的概率

递推公式

dp[i][j]=dp[i−1][j]∗(1−pos[i−1][j])+dp[i][j−1]∗pos[i][j−1]$$dp[i][j]=dp[i-1][j]\ast (1-pos[i-1][j])+dp[i][j-1]\ast pos[i][j-1]$$

sum+=dp[i][j]∗dirty[i][j];$$sum+=dp[i][j]\ast dirty[i][j];$$

最后答案就是sum

对于清洁呢？给每个点设一个值c[i][j]表示点（i，j）的清理的利益，这样只需要找到利益最大的一条路，用sum减去即可

代码

#include<bits/stdc++.h>
using namespace std;
int l,h,k;
double dirty[1005][1005],pos[1006][1005],dp[1005][1005],sum,c[1006][1005],dis[1005][1006];
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int main(){
    scanf("%d%d",&l,&h);
    scanf("%d",&k);
    for(int i=1;i<=l;i++)
    {
        for(int j=1;j<=h;j++)
        {
            dirty[i][j]=read()*1.0;
        }
    }
    for(int i=1;i<=l;i++)
    {
        for(int j=1;j<=h;j++)
        {
            scanf("%lf",&pos[i][j]);
        }
    }
    if(!k) 
    {
        dp[1][1]=1;
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=h;j++)
            {
                if(i==1&&j==1) 
                {
                    sum+=dirty[1][1];
                    continue;
                }
                dp[i][j]=dp[i-1][j]*(1-pos[i-1][j])+dp[i][j-1]*pos[i][j-1];
                sum+=dp[i][j]*dirty[i][j];
            }
        }
        cout<<(int) (sum+0.5);
        return 0;
    }
    else
    {
        dp[1][1]=1;
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=h;j++)
            {
                if(i==1&&j==1) continue;
                dp[i][j]=dp[i-1][j]*(1-pos[i-1][j])+dp[i][j-1]*pos[i][j-1];
                sum+=dp[i][j]*dirty[i][j];c[i][j]=dp[i][j]*dirty[i][j];
                dis[i][j]=max(dis[i-1][j],dis[i][j-1])+c[i][j];
            }
        }
        cout<<(int) (sum-dis[l][h]+0.5);
        return 0;
    }
}