[Luogu 1850] noip16 换教室

[Luogu 1850] noip16 换教室

好久没有更博客了，先唠嗑一会，花了两天的空闲时间大致做完了昨年的noip真题

虽然在经过思考大部分题目都可出解（天天爱跑步除外），但是并不知道考试时候造化如何。

总之自己这段时间多做好事，多积攒RP，每天RP++

Description

Solution：

首先当你看完这个到题的时候，你应该想到先用floyd跑出任意两点的最短路，这个不解释

然后又是这种求期望值最小，很明显也会想到DP的做法

那么DP的方程？通过发现对于当前第i个课程教室的期望是跟前一个课程的选择与否有关的，

那么最后我们的状态可以表示为 f[n][m][0..1]

接下去就比较容易了，只是需要耐心仔细的分类讨论

1、当前的课不换的情况：

（1）上一节课也没换；

（2）上一节课换了----成功 or 不成功；

2、当前的课换的情况：

（1）当前课成功换了：

a、上一节课换了----上一节课成功 or 不成功

b、上一节课没换；

（2）当前的课换了失败：

a、上一节课换了----上一节课成功 or 不成功

b、上一节课没换；

最后总结一下就是

那么就完成了

注意：转移时候因为多次出现距离可预先用cc，cd，dc，dd来表示 c[i-1] 到 c[i] 等等的距离

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=,M=;

 int c[M],d[M],dis[N][N],x,y,z,n,m,v,e;

 double f[M][M][],k[M];

 int main(){

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

     for (int i=;i<=n;++i) scanf("%d",&c[i]);

     for (int i=;i<=n;++i) scanf("%d",&d[i]);

     for (int i=;i<=n;++i) scanf("%lf",&k[i]);

     for (int i=;i<=v;++i) for (int j=;j<=v;++j) dis[i][j]=1e9;

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

         scanf("%d%d%d",&x,&y,&z),dis[x][y]=dis[y][x]=min(dis[x][y],z);

     for (int i=;i<=v;++i) dis[i][i]=;

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

         for (int i=;i<=v;++i) if (i!=kkk)

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

                 if (i!=j&&j!=kkk) dis[i][j]=min(dis[i][kkk]+dis[kkk][j],dis[i][j]);

     for (int i=;i<=n;++i) for (int j=;j<=m;++j) f[i][j][]=f[i][j][]=1e9;

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

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

         int cc=dis[c[i-]][c[i]],cd=dis[c[i-]][d[i]],dc=dis[d[i-]][c[i]],dd=dis[d[i-]][d[i]];

         f[i][][]=f[i-][][]+cc;

         for (int j=;j<=min(i,m);++j){

             f[i][j][]=min(f[i-][j][]+cc,f[i-][j][]+cc*(-k[i-])+dc*k[i-]);

             f[i][j][]=min(f[i-][j-][]+cd*k[i]+cc*(-k[i]),

                            f[i-][j-][]+cc*(-k[i-])*(-k[i])+cd*(-k[i-])*k[i]+

                            dc*k[i-]*(-k[i])+dd*k[i-]*k[i]);

         }

     }

     double ans=1e9;

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

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

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

 }