欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.08.30【SCOI2017】D2T1 花园 (期望DP)

程序员文章站 2022-06-30 20:49:02
...

题目描述

小 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 。
2018.08.30【SCOI2017】D2T1 花园 (期望DP)
特殊性质:0 表示没有特殊性质,1 表示除了最后一行和最后一列的小方块外,所有的小方块的参数都为 0.5 。


解析:

感觉是期望DPDP水题啊。不过作为D2T1D2T1应该还行吧。

ff记录走到每个点的概率。
gg记录走到每个点期望获得的最大脏度。

根据期望的线性性,这样每个点的概率f[i][j]f[i][j]*脏度D[i][j]D[i][j]就是不打扫的期望脏度,打扫的期望脏度减去走到终点的最大期望就行了。

这道题不难,但是要对期望的线性性理解透彻。


代码:

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define gc getchar
#define pc putchar
#define cs const
#define st static

inline
int getint(){
	re int num=0;
	re char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);c=gc())num=(num<<1)+(num<<3)+(c^48);
	return num;
}

inline 
double getdb(){
    re double x=0,y=1.0;
	re char c=0;
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);c=gc())x=x*10+(c^48);
    if(c!='.')return x;
    for(c=gc();isdigit(c);c=gc())x+=(y/=10)*(c^48);
    return x;
}

int l,h;
int k;
double D[1005][1005];
double P[1005][1005],f[1005][1005],g[1005][1005];
double ans;

int main(){
	l=getint();
	h=getint();
	k=getint(); 

	for(int re i=1;i<=l;++i)
	for(int re j=1;j<=h;++j)
	D[i][j]=getint();
	
	for(int re i=1;i<=l;++i)
	for(int re j=1;j<=h;++j)
	P[i][j]=getdb();
	
	ans=D[1][1];
	f[1][1]=1;g[1][1]=D[1][1];
	for(int re i=1;i<=l;++i)
	for(int re j=1;j<=h;++j){
		if(i==1&&j==1)continue;
		f[i][j]=f[i][j-1]*P[i][j-1]+f[i-1][j]*(1-P[i-1][j]);
		ans+=(g[i][j]=f[i][j]*D[i][j]);
		g[i][j]+=max(g[i][j-1],g[i-1][j]);
	}
	printf("%.0lf",ans-g[l][h]*k);
	return 0;
}