题目地址

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

题解

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

#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);
}