【正经题解】换教室
2024-02-23 11:04:57
发布于:浙江
1阅读
0回复
0点赞
期望的计算:如果概率为 的代价为 ,概率为( )的代价为 ,那么期望就是概率乘代价,即
* ( )*
个时段的期望等于每个时段的期望之和,显然的.
于是我们来看这个题
首先有最短路, 暴力预处理 和 之间的距离 [ ][ ]
假如到 个时段已经走了距离 ,那么有可以选择换和不换第 个时段的教室
如果不换,那么显然这一时段的教室只能为
这时上一次分为换和不换两种情况,教室有 [ ]的概率为 和( [ ])的概率为
期望按上面的算就好,教室之间的 乘上概率
如果换第 个时段的教室,那么有 [ ]的概率为 和( [ ])的概率为
然后上一次的同理
这个时候有 [ ] [ ]的概率两个教室分别为 和 [ ]
剩下的情况同理
于是我们设 [ ][ ][ ]为到第 个时段已经换了 个教室的期望, 描述这一次换不换,为 换,为 不换
于是状态转移方程很容易写出
按照上面的描述就好
具体的可以看代码
初值, [ ][ ][ ] [ ][ ][ ] ,其它为 ,很好理解
答案就是 { [ ][ ][ ]}, ... , ...
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=1<<20;//
int n,m,v,e,a[2001],b[2001],dis[2001][2001];
double ans,f[2001][2001][2],c[2001];
inline char gc()//fread加速快读
{
static char BB[1000001],*S=BB,*T=BB;
return S==T&&(T=(S=BB)+fread(BB,1,1000000,stdin),S==T)?EOF:*S++;
}
inline int getin()//普通快读
{
int x=0;char ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=gc();
return x;
}
inline double rgetin()//仿照负数快读写实数快读
{
double x=0;char ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')x=x*10+(ch-48),ch=gc();
if(ch=='.')
{
double l=0.1;
ch=gc();
while(ch>='0'&&ch<='9')x=x+(ch-48)*l,l/=10,ch=gc();
}
return x;
}
int main()
{
n=getin(),m=getin(),v=getin(),e=getin();
for(register int i=1;i<=n;i++)a[i]=getin();//不换的教室
for(register int i=1;i<=n;i++)b[i]=getin();//换的教室
for(register int i=1;i<=n;i++)c[i]=rgetin();//概率
for(register int i=1;i<=v;i++)
for(register int j=1;j<i;j++)
dis[i][j]=dis[j][i]=inf;//dis初始为inf,不用处理dis[i][i]的情况
for(register int i=1;i<=e;i++)
{
register int x,y,w;//从x到y有一条权值为w的边
x=getin(),y=getin(),w=getin(),dis[x][y]=dis[y][x]=min(dis[x][y],w);//无向图,防止重边
}
for(register int k=1;k<=v;k++)
for(register int i=1;i<=v;i++)
for(register int j=1;j<i;j++)//无向图,所以不用处理j>=i
if(dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
for(register int i=1;i<=n;i++)
for(register int j=0;j<=m;j++)
f[i][j][0]=f[i][j][1]=inf;
f[1][0][0]=f[1][1][1]=0;//初始化
for(register int i=2;i<=n;i++)
{
register int mn=min(i,m);
register double w1=dis[a[i-1]][a[i]],
w2=dis[b[i-1]][a[i]]*c[i-1]+dis[a[i-1]][a[i]]*(1-c[i-1]),
w3=dis[a[i-1]][b[i]]*c[i]+dis[a[i-1]][a[i]]*(1-c[i]),
w4=dis[a[i-1]][a[i]]*(1-c[i-1])*(1-c[i])+dis[a[i-1]][b[i]]*(1-c[i-1])*c[i]+dis[b[i-1]][a[i]]*(1-c[i])*c[i-1]+dis[b[i-1]][b[i]]*c[i-1]*c[i];//预先算好加速,这是一个很不好看的递推式
for(register int j=0;j<=mn;j++)
{
f[i][j][0]=min(f[i-1][j][0]+w1,f[i-1][j][1]+w2);
if(j)f[i][j][1]=min(f[i-1][j-1][0]+w3,f[i-1][j-1][1]+w4);
}//正常的dp
}
ans=inf;
for(register int i=0;i<=m;i++)
ans=min(ans,min(f[n][i][0],f[n][i][1]));//统计答案
printf("%.2lf",ans);
}
这里空空如也
有帮助,赞一个