【洛谷P1850】换教室[2016NOIP提高组]

换教室

期望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;

代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define MAXN 2010

 #define MAXV 310

 #define re register

 int n,m,v,e,cla[MAXN],ano[MAXN],dis[MAXV][MAXV];

 inline double min(double x,double y) { return x<y?x:y; }

 double k[MAXN],f[MAXN][MAXN][],ans=1e30;

 int main()

 {

     scanf("%d%d%d%d",&n,&m,&v,&e);

     for(re int i=;i<=n;i++)

      scanf("%d",&cla[i]);

     for(re int i=;i<=n;i++)

      scanf("%d",&ano[i]);

     for(re int i=;i<=n;i++)

      scanf("%lf",&k[i]);

     memset(dis,,sizeof(dis));

     int x,y,w;

     for(int i=;i<=v;i++)

      dis[i][i]=;

     for(int i=;i<=e;i++)

     {

         scanf("%d%d%d",&x,&y,&w);

         if(dis[x][y]>w) dis[x][y]=dis[y][x]=w;

     }

     for(int kk=;kk<=v;kk++)

      for(int i=;i<=v;i++)

       for(int j=;j<=v;j++)

        if(dis[i][j]>dis[i][kk]+dis[kk][j])

        dis[i][j]=dis[i][kk]+dis[kk][j];

     memset(f,,sizeof(f));

     f[][][]=f[][][]=;

     for(int i=;i<=n;i++)

      for(int j=,d=i<m?i:m;j<=d;j++){

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

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

      }

     for(int i=;i<=m;i++)

      ans=min(ans,min(f[n][i][],f[n][i][]));

     printf("%.2lf\n",ans);

     return ;

 }