题解 | 换教室题解

题目地址

https://www.luogu.org/problem/P1850

题解

这题的转移其实挺好想的但是方程特别长...真的特别长...
首先设 $f[i,j,0/1]$ 表示当前在第 $i$ 个位置，申请了 $j$ 次，当前这次申请了/没申请， $a[i]$ 为当前被安排的课室位置， $b[i]$ 为可申请的课室位置， $p[i]$ 为申请通过的概率， $d[i][j]$ 表示 $i$ 到 $j$ 的最短路。 $d[i][j]$ 直接 $floyd$ 一遍求出来就好了。
那么对于 $f[i,j,0]$ ，分类上一次申请了和上一次没有申请两种情况来转移，上一次没申请了就直接转移，上一次申请了就分别讨论申请通过的情况和没通过的情况，然后加起来即可。 $f[i][j][0]=\min \{ f[i-1][j][0]+d[a[i-1]][a[i]],f[i-1][j][1]+d[a[i-1]][a[i]]*(1-p[i-1])+d[b[i-1]][a[i]]*p[i-1]\}$
对于 $f[i,j,1]$ ，共四种情况需要组合，并且因为两次申请互相独立，所以需要乘法原理乘起来（我第一次就是写成了加法然后挂掉了）。 $f[i][j][1]=\min(f[i-1][j-1][0]+d[a[i-1]][b[i]]*p[i]+d[a[i-1]][a[i]]*(1-p[i]),f[i-1][j-1][1]+d[a[i-1]][a[i]]*(1-p[i-1])*(1-p[i])+d[a[i-1]][b[i]]*p[i]*(1-p[i-1])+d[b[i-1]][a[i]]*(p[i-1])*(1-p[i])+d[b[i-1]][b[i]]*p[i-1]*p[i])$

#include <bits/stdc++.h>
using namespace std;

int d[310][310];
int a[2010], b[2010];
int n, m, V, E;
double p[2010], f[2010][2010][2];
// f[i][j][0/1] 表示第i间教室换了j次这次换/不换

int main() {
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d%d%d", &n, &m, &V, &E);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    for(int u, v, w, i = 1; i <= E; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        d[v][u] = d[u][v] = min(d[u][v], w);
    }
    for(int i = 1; i <= V; ++i) d[i][i] = d[i][0] = d[0][i] = 0;
    for(int k = 1; k <= V; ++k) 
        for(int i = 1; i <= V; ++i) 
            for(int j = 1; j <= V; ++j) 
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for(int i = 0; i <= n; ++i) for(int j = 0; j <= m; ++j) 
        f[i][j][0] = f[i][j][1] = 1e17;
    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] + d[a[i - 1]][a[i]];
        for(int j = 1; j <= min(i, m); ++j) {
            f[i][j][0] = min(f[i][j][0], min(f[i-1][j][0]+d[a[i-1]][a[i]], f[i-1][j][1]+d[a[i-1]][a[i]]*(1-p[i-1])+d[b[i-1]][a[i]]*p[i-1]));
            f[i][j][1] = min(f[i][j][1], min(f[i-1][j-1][0]+d[a[i-1]][b[i]]*p[i]+d[a[i-1]][a[i]]*(1-p[i]), 
                               f[i-1][j-1][1]+d[a[i-1]][a[i]]*(1-p[i-1])*(1-p[i])+d[a[i-1]][b[i]]*p[i]*(1-p[i-1])+d[b[i-1]][a[i]]*(p[i-1])*(1-p[i])+d[b[i-1]][b[i]]*p[i-1]*p[i]));
        }
    }
    double ans = 1e17;
    for(int i = 0; i <= m; ++i) ans = min(ans, min(f[n][i][0], f[n][i][1]));
    printf("%.2lf\n", ans);
}