[NOIP2016TG] 洛谷 P1850 换教室

骑猪看日落 2023-08-17 17:49 102阅读 0赞

[https://www.luogu.org/problem/P1850][https_www.luogu.org_problem_P1850]

题意？太长懒得概括。

### 期望概述 ###

期望，记为\\(E(x)\\),是对于若干个概率事件，结果与概率之积的总和。

期望的数学意义是：对于一个结果均匀分布的事件，期望是无数次实验结果的平均值。

对于非均匀分布的事件，期望反映平均取值的大小。

掷骰tou子结果的平均数为3.5，这类问题说明非均匀分布事件的期望值可能不等于任何一个结果。

（以上为个人理解，可能有误，欢迎指正）

### 分析 ###

Floyd求最短路略。

首先明确，对于一个要换教室的集合，直接计算期望值是很难的。当然，可以枚举所有子集再计算，可是。。会TLE。所以考虑用递推（动态规划）的方式计算答案。

当前教室与之前教室都不换，答案为确定的距离，直接得出

\\(cost=dis\[c\[i-1\]\]\[c\[i\]\]\\)

在当前教室i选择更换的情况下，可能成功也可能失败，则期望值是

\\(cost=dis\[c\[i-1\]\]\[c\[i\]\]\*(1-k\[i\])+dis\[c\[i-1\]\]\[d\[i\]\]\*k\[i\]\\)

在前一个教室选择更换的情况下，相应地有

\\(cost=dis\[c\[i-1\]\]\[d\[i\]\]\*k\[i\]+dis\[c\[i-1\]\]\[c\[i\]\]\*(1-k\[i\])\\)

而如果前一个教室选择更换，也相应会有两种情况。由乘法原理可以得到四种情况，相加则是

\\(cost=dis\[c\[i-1\]\]\[c\[i\]\]\*(1-k\[i-1\])\*(1-k\[i\])\\)

\\(+dis\[c\[i-1\]\]\[d\[i\]\]\*(1-k\[i-1\])\*k\[i\]\\)

\\(+dis\[d\[i-1\]\]\[c\[i\]\]\*(1-k\[i\])\*k\[i-1\]\\)

\\(+dis\[d\[i-1\]\]\[d\[i\]\]\*k\[i-1\]\*k\[i\]\\)

我们根据当前节点是否选择，将上述代价分为两组。根据题意，还有两维：当前教室和已经更换的教室数目。即

\\(f\[i\]\[j\]\[k\](k\\in\\\{0,1\\\})\\)

表示第i个教室之前，更换了j个教室，是否更换第i个教室的最小期望代价。

综上所述，状态转移方程为

f[i][j][0]=min(f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]),f[i-1][j][0]+dis[c[i-1]][c[i]]) f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1-k[i]),f[i-1][j-1][1]+dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]+dis[d[i-1]][d[i]]*k[i-1]*k[i]) //如果阅读不方便请看上文的LATEX

### 代码 ###

惯例：仍然是抄的

//注：本题的状态定义为浮点数，要注意数据类型的转换 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=2005,MAXV=305; int n,m,v,e; int c[MAXN],d[MAXN]; double ans=1e9,k[MAXN],f[MAXN][MAXN][2],dis[MAXV][MAXV];//dis为距离 int x,y,z; int main() { scanf("%d %d %d %d",&n,&m,&v,&e); for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) dis[i][j]=1e9; for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) scanf("%lf",&k[i]); for(int i=1;i<=e;i++) { scanf("%d %d %d",&x,&y,&z); dis[y][x]=min(dis[y][x],(double)z); dis[x][y]=min(dis[x][y],(double)z);//处理重边 } for(int i=1;i<=v;i++) dis[i][i]=0;//处理自环 for(int t=1;t<=v;t++) for(int i=1;i<=v;i++) for(int j=1;j<i;j++) if(dis[i][t]+dis[t][j]<dis[i][j]) dis[i][j]=dis[j][i]=dis[i][t]+dis[t][j];//Floyd for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) f[i][j][1]=f[i][j][0]=1e9; f[1][0][0]=f[1][1][1]=0;//初始化 for(int i=2;i<=n;i++) for(int j=0;j<=m&&j<=i;j++) { f[i][j][0]=min(f[i-1][j][1]+dis[d[i-1]][c[i]]*k[i-1]+dis[c[i-1]][c[i]]*(1-k[i-1]),f[i-1][j][0]+dis[c[i-1]][c[i]]); if(j) f[i][j][1]=min(f[i-1][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1-k[i]),f[i-1][j-1][1]+dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]+dis[d[i-1]][d[i]]*k[i-1]*k[i]); //状态转移 } for(int i=0;i<=m;i++) ans=min(min(ans,f[n][i][1]),f[n][i][0]);//答案更换的教室数目不确定 printf("%.2lf",ans); return 0; }

最后，祝大家身体健康，再见。

转载于:https://www.cnblogs.com/ehznehc/p/11484067.html

[https_www.luogu.org_problem_P1850]: https://www.luogu.org/problem/P1850