「NOIP2016」换教室

传送门
Luogu

解题思路

这是一道概率期望相关的 \(\text{DP}\)
首先 \(\text{Floyd}\) 预处理一下两点的最短距离。
然后考虑如何 \(\text{DP}\)。
我们设 \(dp[i][j][0/1]\) 表示当前处理到第 \(i\) 个时间点，申请了 \(j\) 次换地点，第 \(i\) 次没申请/申请的期望最小代价。
转移方程就是：

dp[i][j][0] = min(
    dp[i - 1][j][0] + dis[c1][c2],
    dp[i - 1][j][1] + (1.0 - p[i - 1]) * dis[c1][c2] 
                    + p[i - 1] * dis[d1][c2]
);
dp[i][j][1] = min(
    dp[i - 1][j - 1][0] + (1.0 - p[i]) * dis[c1][c2]
                        + p[i] * dis[c1][d2],
    dp[i - 1][j - 1][1] + (1.0 - p[i]) * (1.0 - p[i - 1]) * dis[c1][c2]
                        + (1.0 - p[i]) * p[i - 1] * dis[d1][c2]
                        + p[i] * (1.0 - p[i - 1]) * dis[c1][d2]
                        + p[i] * p[i - 1] * dis[d1][d2]
);

至于为什么直接上代码太长了不想打

细节注意事项

• 咕咕咕

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
    s = f ? -s : s;
}

const int _ = 2000 + 10;
const int __ = 300 + 10;

double p[_], dp[_][_][2];
int n, m, V, E, c[_], d[_], dis[__][__];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    read(n), read(m), read(V), read(E);
    for (rg int i = 1; i <= n; ++i) read(c[i]);
    for (rg int i = 1; i <= n; ++i) read(d[i]);
    for (rg int i = 1; i <= n; ++i) scanf("%lf", p + i);
    memset(dis, 0x3f, sizeof dis);
    for (rg int u, v, w; E--; ) read(u), read(v), read(w), dis[v][u] = dis[u][v] = min(dis[u][v], w);
    for (rg int i = 1; i <= V; ++i) dis[i][i] = 0;
    for (rg int k = 1; k <= V; ++k)
        for (rg int i = 1; i <= V; ++i)
            for (rg int j = 1; j <= V; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    memset(dp, 127, sizeof dp);
    dp[1][0][0] = dp[1][1][1] = 0;
    for (rg int i = 2; i <= n; ++i) {
        int c1 = c[i - 1], c2 = c[i];
        int d1 = d[i - 1], d2 = d[i];
        dp[i][0][0] = dp[i - 1][0][0] + dis[c[i - 1]][c[i]];
        for (rg int j = 1; j <= min(i, m); ++j) {
            dp[i][j][0] = min(
                dp[i - 1][j][0] + dis[c1][c2],
                dp[i - 1][j][1] + (1.0 - p[i - 1]) * dis[c1][c2] + p[i - 1] * dis[d1][c2]
                );
            dp[i][j][1] = min(
                dp[i - 1][j - 1][0] + (1.0 - p[i]) * dis[c1][c2] + p[i] * dis[c1][d2],
                dp[i - 1][j - 1][1] + (1.0 - p[i]) * (1.0 - p[i - 1]) * dis[c1][c2]
                + (1.0 - p[i]) * p[i - 1] * dis[d1][c2]
                + p[i] * (1.0 - p[i - 1]) * dis[c1][d2]
                + p[i] * p[i - 1] * dis[d1][d2]
                );
        }
    }
    double ans = 1e100;
    for (rg int j = 0; j <= m; ++j)
        ans = min(ans, min(dp[n][j][0], dp[n][j][1]));
    printf("%.2lf\n", ans);
    return 0;
}

完结撒花 \(qwq\)

「NOIP2016」换教室

原文：https://www.cnblogs.com/zsbzsb/p/11746547.html