NOIP2016 提高组换教室 (BZOJ 4720)

题目链接：BZOJ：http://www.lydsy.com/JudgeOnline/problem.php?id=4720 洛谷：https://www.luogu.org/problem/show?pid=1850

题意：给一张无向图，有 n 个时间，对于第 i 个时间，要去地点 c[i]，每条边都有一个权值。同时，每个时间还有一个备用地址 d[i]，有 m 次申请机会，通过几率为 k[i]，问总消耗的期望是多少...

本题考试的时候连 floyd 都不会... 强行水了前几个点 qwq 现在一看好水，结果一发 32pts...

坑有点多，调了 1h30min 左右... 我还是太弱了 qwq 具体犯过的智障错误有：inf 开小了,inf 开大了, 数组开小了, 数组开大了等......

下面是正式题解：

首先用 floyd 预处理出两点距离 dis 备用，我们考虑怎么转移...

dp[i][j][0/1] 表示目前时间点为 i，申请了 j 次，且本次不通过/通过

式子很好想，但是需要考虑好多情况...

dp[i][j][0]=min(上次没有申请，上次申请了通过+不通过)

dp[i][j][1]=min(上次没有申请，通过通过+不通过通过+通过不通过+不通过不通过)

具体式子在代码里...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2010
#define inf 1000000000
using namespace std;
int n,m,v,e,c[N],d[N],dis[310][310];
double k[N],dp[N][N][2];
void pre()
{
	for(int i=0;i<=v;i++)
     	for(int j=0;j<=v;j++)
     	dis[i][j]=inf;
 	for(int i=1;i<=v;i++)dis[i][i]=0;
    for(int i=0;i<=n;i++)
     	for(int j=0;j<=n;j++)
     	dp[i][j][0]=dp[i][j][1]=inf;
    dp[1][0][0]=dp[1][1][1]=0;
}
void floyd()
{
	for(int t=1;t<=v;t++)
     for(int i=1;i<=v;i++)
      for(int j=1;j<=v;j++)
      dis[i][j]=min(dis[i][j],dis[i][t]+dis[t][j]);
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&v,&e);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    for(int i=1;i<=n;i++)scanf("%lf",&k[i]); 
	pre();
    for(int i=1;i<=e;i++)
    {
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        if(a==b)continue;
        if(w<dis[a][b])dis[a][b]=w;
        dis[b][a]=dis[a][b];
    }
    floyd();
    for(int i=2;i<=n;i++)
    {
    	dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];
     	for(int j=1;j<=min(m,i);j++)
      	{
         	dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i-1])*dis[c[i-1]][c[i]]);
         	dp[i][j][1]=min(dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]+k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]);
        }
    }
    double ans=dp[n][0][0];
    for(int i=1;i<=m;i++)
    {ans=min(ans,dp[n][i][0]);ans=min(ans,dp[n][i][1]);}
    printf("%.2lf",ans);    
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2010

#define inf 1000000000

using namespace std;

int n,m,v,e,c[N],d[N],dis[310][310];

double k[N],dp[N][N][2];

void pre()

{

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

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

dis[i][j]=inf;

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

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

for(int j=0;j<=n;j++)

dp[i][j][0]=dp[i][j][1]=inf;

dp[1][0][0]=dp[1][1][1]=0;

}

void floyd()

{

for(int t=1;t<=v;t++)

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

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

dis[i][j]=min(dis[i][j],dis[i][t]+dis[t][j]);

}

int main()

{

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

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

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

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

pre();

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

{

int a,b,w;

scanf("%d %d %d",&a,&b,&w);

if(a==b)continue;

if(w<dis[a][b])dis[a][b]=w;

dis[b][a]=dis[a][b];

}

floyd();

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

{

dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];

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

{

dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1.0-k[i-1])*dis[c[i-1]][c[i]]);

dp[i][j][1]=min(dp[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1.0-k[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1.0-k[i-1])*(1.0-k[i])*dis[c[i-1]][c[i]]+k[i-1]*(1.0-k[i])*dis[d[i-1]][c[i]]+(1.0-k[i-1])*k[i]*dis[c[i-1]][d[i]]);

}