题解 P1850 【换教室】
我想发一个吊打给我们出题的人的题解就是这样@Refun
少年，你知道什么叫效率么
168ms 空间3M rk1的题解
首先这是个经典期望dp
其实这题应该是绿题不该是蓝题
只要知道期望dp的基本套路就能做
期望的计算:如果概率为k的代价为w1,概率为(1-k)的代价为w2，那么期望就是概率乘代价，即
kw1+(1-k)w2
n个时段的期望等于每个时段的期望之和，显然的.
于是我们来看这个题
首先有最短路，floyed暴力预处理x和y之间的距离dis[x][y]
假如到i-1个时段已经走了距离d，那么有可以选择换和不换第i个时段的教室
如果不换，那么显然这一时段的教室只能为ci
这时上一次分为换和不换两种情况，教室有k[i-1]的概率为di和(1-k[i-1])的概率为ci
期望按上面的算就好,教室之间的dis乘上概率
如果换第i个时段的教室，那么有k[i]的概率为di和(1-k[i])的概率为ci
然后上一次的同理
这个时候有k[i]k[i-1]的概率两个教室分别为di和d[i-1]
剩下的情况同理
于是我们设f[i][j][k]为到第i个时段已经换了j个教室的期望，k描述这一次换不换，为0换，为1不换
于是状态转移方程很容易写出
按照上面的描述就好
具体的可以看代码
初值，f[1][1][1]=f[1][0][0]=0,其它为inf，很好理解
答案就是max{f[n][i][k]},i=0...m,k=0...1
// luogu-judger-enable-o2
#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);
}如果做到这里，已经稳A了
但还不够快！
我们看到f[i][j][k]的值只和f[i-1][j,j-1][0,1]有关
所以滚动数组优化一波
保证f[i][j][k]是由上一次的递推过来，所以j倒着循环即可，和01背包是一样的
这个样子空间就优化到了一维，速度也提高了不少，虽然还是要看脸
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=1<<20;
int n,m,v,e,a[2001],b[2001],dis[301][301];
double ans,f[2001][2],c[2001];
inline char gc()
{
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;
for(register int i=1;i<=e;i++)
{
register int 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++)
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 j=0;j<=m;j++)
f[j][0]=f[j][1]=inf;
f[0][0]=f[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=mn;j>=0;j--)
{
f[j][0]=min(f[j][0]+w1,f[j][1]+w2);
if(j)f[j][1]=min(f[j-1][0]+w3,f[j-1][1]+w4);
}
}
ans=inf;
for(register int i=0;i<=m;i++)
ans=min(ans,min(f[i][0],f[i][1]));
printf("%.2lf",ans);
}