换教室[2016NOIP提高组](洛谷P1850)

时间:2022-12-16 23:39:10

换教室

期望DP

状态:

f[i][j][0/1]表示前i节课 提交j个申请 第i个教室不申请/申请(为了确定当前教室,方便转移) 的最小期望

方程:

f[i][j][0]=min(f[i-1][j][0]+dis[cla[i-1]][cla[i]],f[i-1][j][1]+dis[ano[i-1]][cla[i]]*k[i-1]+dis[cla[i-1]][cla[i]]*(1-k[i-1]));
f[i][j][1]=min(f[i-1][j-1][0]+dis[cla[i-1]][ano[i]]*k[i]+dis[cla[i-1]][cla[i]]*(1-k[i]),f[i-1][j-1][1]+(dis[ano[i-1]][ano[i]]*k[i]+dis[ano[i-1]][cla[i]]*(1-k[i]))*k[i-1]+(dis[cla[i-1]][ano[i]]*k[i]+dis[cla[i-1]][cla[i]]*(1-k[i]))*(1-k[i-1]));

边界:

f[1][0][0]=f[1][1][1]=0;

代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define MAXN 2010
 6 #define MAXV 310
 7 #define re register
 8 int n,m,v,e,cla[MAXN],ano[MAXN],dis[MAXV][MAXV];
 9 inline double min(double x,double y) { return x<y?x:y; }
10 double k[MAXN],f[MAXN][MAXN][2],ans=1e30;
11 int main()
12 {
13     scanf("%d%d%d%d",&n,&m,&v,&e);
14     for(re int i=1;i<=n;i++)
15      scanf("%d",&cla[i]);
16     for(re int i=1;i<=n;i++)
17      scanf("%d",&ano[i]);
18     for(re int i=1;i<=n;i++)
19      scanf("%lf",&k[i]);
20     memset(dis,1,sizeof(dis));
21     int x,y,w;
22     for(int i=1;i<=v;i++)
23      dis[i][i]=0;
24     for(int i=1;i<=e;i++)
25     {
26         scanf("%d%d%d",&x,&y,&w);
27         if(dis[x][y]>w) dis[x][y]=dis[y][x]=w;
28     }
29     for(int kk=1;kk<=v;kk++)
30      for(int i=1;i<=v;i++)
31       for(int j=1;j<=v;j++)
32        if(dis[i][j]>dis[i][kk]+dis[kk][j])
33        dis[i][j]=dis[i][kk]+dis[kk][j];
34     memset(f,127,sizeof(f));
35     f[1][0][0]=f[1][1][1]=0;
36     for(int i=2;i<=n;i++)
37      for(int j=0,d=i<m?i:m;j<=d;j++){
38          f[i][j][0]=min(f[i-1][j][0]+dis[cla[i-1]][cla[i]],f[i-1][j][1]+dis[ano[i-1]][cla[i]]*k[i-1]+dis[cla[i-1]][cla[i]]*(1-k[i-1]));
39          if(j) f[i][j][1]=min(f[i-1][j-1][0]+dis[cla[i-1]][ano[i]]*k[i]+dis[cla[i-1]][cla[i]]*(1-k[i]),f[i-1][j-1][1]+(dis[ano[i-1]][ano[i]]*k[i]+dis[ano[i-1]][cla[i]]*(1-k[i]))*k[i-1]+(dis[cla[i-1]][ano[i]]*k[i]+dis[cla[i-1]][cla[i]]*(1-k[i]))*(1-k[i-1]));
40      }
41     for(int i=0;i<=m;i++)
42      ans=min(ans,min(f[n][i][0],f[n][i][1]));
43     printf("%.2lf\n",ans);
44     return 0;
45 }