ShineEternal的小书屋

ShineEternal的小书屋

https://blog.csdn.net/kkkksc03

题解 P1850 【换教室】

posted on 2019-10-25 19:04:14 | under 题解 |

$My\ blog$

天哪这道题真的是神仙。。。

orz出题人

能出这种dp转移都写吐血的题目真的tql

description:

给出n个时间段,可申请m次换课,每次换课可申请从 $c[i]$ 换到 $d[i]$ ,并有 $k[i]$ 的概率换课成功,每个教室有间距,问路程期望的最小值。

solution:

首先这就是一道期望dp题。

说到期望,

https://45475.blog.luogu.org/mathematical-expectation

这篇日报大概会给你不少的启发。

考虑Dp

设 $f[i][j][0/1]$ 表示前i节课申请了j次,第i次是否申请的期望最优解。

则:

$$f[i][j][0]=\min(f[i][j][0],f[i-1][j][0]+a[c[i-1]][c[i]],f[i-1][j][1]+(1-k[i-1])*a[c[i-1]][c[i]]+k[i-1]*a[d[i-1]][c[i]])$$

从两种情况转移而来:

  • 上一次没申请换课,那么这两次直接都从 $c$ 的规定走就行了。

  • 上一次申请换课了:

1、通过了,那么就从上一次的d到现在的c

2、没通过,跟上一次没申请一样

$$f[i][j][1]=\min(f[i][j][1],f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]],f[i-1][j-1][1]+k[i-1]*k[i]*a[d[i-1]][d[i]]+k[i-1]*(1-k[i])*a[d[i-1]][c[i]]+(1-k[i-1])*k[i]*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]])$$

重要提示:

dp式子真的很长,当然放在代码里写的应该比较短,会尽全力解释,但可以移步代码查看分步式子。

还是分两种:

  • 上一次没申请:

1、这次通过了,那么从上一次的c到现在的d

2、没通过,c到c

  • 上一次申请了:

现在热闹了

上一次申请的两种情况:

$$(1-k[i-1])\times c[i-1],k[i-1]*d[i-1]$$

这次申请的两种情况:

$$(1-k[i])\times c[i],k[i]*d[i]$$

现在,只要两两组合即可,共有 $2\times2=4$ 种来源。

a数组是什么?

这是两点间距离数组,观察到教室数较少,Floyd求出即可

code:

#include<cstdio>
#include<algorithm>
using namespace std;
double k[2005],a[305][305];
double f[2005][2005][2];
int c[2005],d[2005];
int main()
{
    int n,m,v,e;
    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]);
    }
    for(int i=1;i<=301;i++)
    {
        for(int j=1;j<=301;j++)
        {
            a[i][j]=1000000000;
        }
    } 
    for(int i=1;i<=300;i++)
    a[i][i]=0; 
    for(int i=1;i<=e;i++)
    {
        int x,y;
        double z;
        scanf("%d%d%lf",&x,&y,&z);
        a[x][y]=a[y][x]=min(a[x][y],z);
    }

    for(int kk=1;kk<=v;kk++)
    {
        for(int i=1;i<=v;i++)
        {
            for(int j=1;j<=v;j++)
            {
                a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j][0]=f[i][j][1]=1000000000;
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=min(i,m);j++)
        {
            f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+a[c[i-1]][c[i]]);
            f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+(1-k[i-1])*a[c[i-1]][c[i]]+k[i-1]*a[d[i-1]][c[i]]);
            if(j)
            {
                f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*a[c[i-1]][d[i]]+(1-k[i])*a[c[i-1]][c[i]]);
                f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+k[i-1]*k[i]*a[d[i-1]][d[i]]+k[i-1]*(1-k[i])*a[d[i-1]][c[i]]+(1-k[i-1])*k[i]*a[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*a[c[i-1]][c[i]]);
            }
        }
    }
    double ans=1000000000;
    for(int i=0;i<=m;i++)
    {
        ans=min(ans,f[n][i][1]);
        ans=min(ans,f[n][i][0]);
    }
    printf("%.2lf\n",ans);
    return 0;
}