普通动态规划与递推|[NOIP2016]换教室
题目大意 有 n 个时间段，第 i 个时间段可以选择在 ci 教室上课，也可以选择申请换课，有 ki 概率申请通过，在 di 上课，另外 1?ki 的概率留在 ci 教室。
总共有 v 个教室， e 条路径双向联通教室 xi 和 yi ，路径有权值 wi 。在课间时（相邻两个时间段的间隔中），你要从上一个教室走最短路径到下一个教室。
现在你有 m 次申请机会，只能提前申请一堆换课（也就是你不能在知道某一次申请结果后再去申请下一个换课）。求总距离的最小期望。
【普通动态规划与递推|[NOIP2016]换教室】 1≤n≤2000,0≤m≤2000,1≤v≤300,0≤e≤90000,1≤wi≤100,0≤ki≤1
题目分析 这题是很水的期望题。
由期望的线性性
E[X]=∑i=2nE[dis(i?1,i)]
因此我们可以分开来计算每一个课间的期望距离。
令 fi,j,0/1表示当前在第 i个时间段，已经申请了 j次，这个时间段是否申请的最小期望。
然后直接枚举上一个课间是否申请，分类讨论各自的概率（申请包括了是否通过）转移就好了。这个很简单，相信大家都懂。
至于最短路，直接上 Floyd。
时间复杂度 O(v3+nm)。
代码实现
#include
#include
#include
#include
#include using namespace std;
typedef double db;
int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}const int INF=INT_MAX/3;
const db FINF=DBL_MAX/3;
const int N=2005;
const int M=2005;
const int V=305;
const int E=90005;
db f[N][M][2];
int dis[V][V];
int c[N],d[N];
int n,m,v,e;
db p[N];
db ans;
void floyd()
{
for (int k=1;
k<=v;
k++)
for (int i=1;
i<=v;
i++)
if (i!=k)
for (int j=1;
j<=v;
j++)
if (i!=j&&j!=k)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}void dp()
{
for (int i=1;
i<=n;
i++)
for (int j=0;
j<=m;
j++)
f[i][j][0]=f[i][j][1]=FINF;
f[1][0][0]=f[1][1][1]=0;
for (int i=2;
i<=n;
i++)
for (int j=0;
j<=i&&j<=m;
j++)
{
int dxu=dis[c[i-1]][c[i]],dxv=dis[c[i-1]][d[i]],dyu=dis[d[i-1]][c[i]],dyv=dis[d[i-1]][d[i]];
db p1=p[i-1],p2=p[i];
if (j<=i-1) f[i][j][0]=min(p1*dyu+(1-p1)*dxu+f[i-1][j][1],dxu+f[i-1][j][0]);
if (j) f[i][j][1]=min(f[i-1][j-1][0]+p2*dxv+(1-p2)*dxu,f[i-1][j-1][1]+p1*p2*dyv+p1*(1-p2)*dyu+(1-p1)*p2*dxv+(1-p1)*(1-p2)*dxu);
}
ans=FINF;
for (int j=0;
j<=m&&j<=n;
j++) ans=min(ans,min(f[n][j][0],f[n][j][1]));
}int main()
{
freopen("classroom.in","r",stdin),freopen("classroom.out","w",stdout);
n=read(),m=read(),v=read(),e=read();
for (int i=1;
i<=n;
i++) c[i]=read();
for (int i=1;
i<=n;
i++) d[i]=read();
for (int i=1;
i<=n;
i++) scanf("%lf",&p[i]);
for (int i=1;
i<=v;
i++)
{
for (int j=1;
j<=v;
j++)
dis[i][j]=INF;
dis[i][i]=0;
}
for (int i=1,x,y,z;
i<=e;
i++) x=read(),y=read(),z=read(),dis[x][y]=min(dis[x][y],z),dis[y][x]=min(dis[y][x],z);
floyd(),dp();
printf("%.2lf\n",ans);
fclose(stdin),fclose(stdout);
return 0;
} 推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 第326天
- Shell-Bash变量与运算符
- live|live to inspire 一个普通上班族的流水账0723
- 逻辑回归的理解与python示例
- 其实你就是个普通人
- Guava|Guava RateLimiter与限流算法
- 我和你之前距离