zcmimi's blog

查看原题

点击跳转

f(i,j,0),f(i,j,1)表示:

i个时间段,已经用了j个机会,选择c_i与选择d_i(换/不换教室)的最小期望

dis(i,j)表示i,j之间最短距离

转移方程:

f(i,j,0)=\min \begin{cases} f(i-1,j,0)+dis(c_{i-1},c_i)\\ \begin{aligned} f(i-1,j,1) &+dis(d_{i-1},c_i)\times k_{i-1}\\ &+dis(c_{i-1},c_i)\times(1-k_{i-1}) \end{aligned} \end{cases}

f(i,j,1)=\min \begin{cases} \begin{aligned} f(i-1,j-1,0) &+dis(c_{i-1},d_i)\times k_i\\ &+dis(c_{i-1},c_i)\times (1-k_i) \end{aligned}\\ \begin{aligned} f(i-1,j-1,1) &+dis(d_{i-1},d_i)\times k_{i-1}\times k_i\\ &+dis(c_{i-1},d_i)\times (1-k_{i-1})\times k_i\\ &+dis(d_{i-1},c_i)\times k_{i-1}\times (1-k_i)\\ &+dis(c_{i-1},c_i)\times (1-k_{i-1})\times (1-k_i)\\ \end{aligned} \end{cases}

#include<bits/stdc++.h>
const int N=2011,V=311;
int n,m,v,e,c[N],d[N],dis[V][V];
double k[N],f[N][N][2];
template<class T>void cmin(T&x,T y){if(y<x)x=y;}
template<class T>T min(T x,T y){return x<y?x:y;}
int main(){
    // read
    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);
    //init
    memset(dis,63,sizeof dis);
    for(int i=1,x,y,w;i<=e;++i)
        scanf("%d%d%d",&x,&y,&w),
        cmin(dis[x][y],w),cmin(dis[y][x],w);
    for(int k=1;k<=v;++k)
        for(int i=1;i<=v;++i)
            for(int j=1;j<=v;++j)if(i!=j&&j!=k)
                cmin(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=v;++i)dis[i][i]=dis[i][0]=dis[0][i]=0;
    //solve
    memset(f,126,sizeof f);
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=n;++i){
        f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
        for(int j=1;j<=min(m,i);++j)
            f[i][j][0]=min(
                f[i-1][j][0]+dis[c[i-1]][c[i]],
                f[i-1][j][1]
                    +dis[d[i-1]][c[i]]*k[i-1]
                    +dis[c[i-1]][c[i]]*(1-k[i-1])
            ),
            f[i][j][1]=min(
                f[i-1][j-1][0]
                    +dis[c[i-1]][d[i]]*k[i]
                    +dis[c[i-1]][c[i]]*(1-k[i]),
                f[i-1][j-1][1]
                    +dis[d[i-1]][d[i]]*k[i-1]*k[i]
                    +dis[c[i-1]][d[i]]*(1-k[i-1])*k[i]
                    +dis[d[i-1]][c[i]]*k[i-1]*(1-k[i])
                    +dis[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])
            );
    }
    double ans=1e17;
    for(int i=0;i<=m;++i)
        cmin(ans,min(f[n][i][0],f[n][i][1]));
    printf("%.2f",ans);
}
LG 1850 换教室
comment评论
Search
search