[NOIP 2016] 换教室：数学期望，DP

题意：一共有v间教室，e条有长度的双向通道，可能有重边和自环（v≤300，e≤90000）。n节课（n≤2000），每节课有两间教室可选，默认为c[i]，可申请更换为d[i]，申请要么通过要么不通过，通过的概率是p[i]，所有申请在开始所有课程之前提交。求提交的申请不超过m个的前提下，依次上完这n节课途经距离的期望的最小值。

考试时只有40分钟留给我做这一题了。个人的相关数学背景知识仅限于离散期望的定义。没有多想，来了个44分暴力。最后时间紧急，连大样例都没测。民间数据有的几十分，有的几分，这时我就知道写挂了……官方数据是20分。前几天忽然想起，我好像没有处理m个申请这个限制？看了一下源代码，果然如此QAQ 还有分，感谢当时那个随机数种子……

这道题有一个很明显的多阶段决策问题模型，我们可以采用动态规划技术。和背包问题类似，这两维是必须的：前i节课，不超过j个申请。这里定义为恰好j个申请也可以，我采用的是前者。

第i节课，要么申请更换，要么不申请。也许应该把这个决策纳入状态？可是上节课在哪里呢？如果申请上节课更换，有一定概率成功，一定概率不成功，如何计算转移的代价？

第i节课，要么在c[i]上，要么在d[i]上。把教室纳入状态，凑了几个意义不明的转移方程，开始写。写着写着放弃了……

瞥了一眼题解，不是很懂。但是灵光一现……为什么不分三类呢？不申请，申请且成功，申请且失败。嗯，看起来很靠谱。但是大样例WA。debug几处手误，依然WA。大概不是写挂了，于是又看了看题解，发现大家使用的是上述第一种状态定义。

不明白这样做的正确性，我想先搞明白分三类的错误性。问了一下当场做出此题的马老师，他说他当时也是先这么写的，发现不对，于是推翻重写做出正解Orz 他说，问题在于“所有的申请只能在学期开始前一次性提交”。从道理上来讲，应该就是这样，但我想知道分三类究竟是以何种方式影响了算法的正确性，计算出来的又是什么东西呢？

如果已知策略，求期望，分三类递推是正确的。然而，如果要做出决策，在多种决策之间取min，就会出问题：也许申请且成功的最优决策由上节课申请转移而来，而申请且失败的最优决策由上节课不申请转移而来；本节课向下节课转移时，上节课究竟是申请还是不申请呢？

去掉“一次性提交”的限制，这样做就对吗？值得商榷。我还没想清楚。

再来说说正解的正确性。我们要求的是路径长度的期望，不妨将路径长度拆成两部分：1~n-1和n-1~n。由期望的线性性质，两个变量之和的期望等于两个变量期望之和。这就是原理。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAX_N = , MAX_M = , MAX_V = , MAX_W = ;
const double inf = ;
int c[MAX_N+][], dis[MAX_V+][MAX_V+];
double p[MAX_N+], f[MAX_N+][MAX_M+][];

template<typename T>
inline void relax(T& x, T v)
{
    x = min(x, v);
}

inline int dist(int k, int s, int t)
{
    return dis[c[k-][s]][c[k][t]];
}

int main()
{
    int n, m, e, v;
    scanf("%d %d %d %d", &n, &m, &v, &e);
    for (int i = ; i < ; ++i)
        for (int j = ; j <= n; ++j)
            scanf("%d", &c[j][i]);
    for (int i = ; i <= n; ++i)
        scanf("%lf", &p[i]);

    for (int i = ; i <= v; ++i)
        for (int j = ; j <= v; ++j)
            dis[i][j] = MAX_W*MAX_V;

    for (int i = ; i <= v; ++i)
        dis[i][i] = ;

    for (int i = ; i < e; ++i) {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        relax(dis[a][b], w);
        relax(dis[b][a], w);
    }

    for (int k = ; k <= v; ++k)
        for (int i = ; i <= v; ++i)
            for (int j = ; j <= v; ++j)
                relax(dis[i][j], dis[i][k] + dis[k][j]);

    for (int j = ; j <= m; ++j)
        f[][j][] = inf;
    for (int i = ; i <= n; ++i) {
        f[i][][] = f[i-][][] + dist(i, , );
        f[i][][] = inf;
        for (int j = ; j <= m; ++j) {
            f[i][j][] = f[i][j-][];
            relax(f[i][j][], min(f[i-][j][] + dist(i, , ), f[i-][j][] + p[i-]*dist(i, , ) + (-p[i-])*dist(i, , )));
            f[i][j][] = f[i][j-][];
            relax(f[i][j][], min(f[i-][j-][] + p[i]*dist(i, , ) + (-p[i])*dist(i, , ),
                f[i-][j-][] + p[i-]*p[i]*dist(i, , ) + p[i-]*(-p[i])*dist(i, , ) + (-p[i-])*p[i]*dist(i, , ) + (-p[i-])*(-p[i])*dist(i, , )));
        }
    }

    printf("%.2f\n", min(f[n][m][], f[n][m][]));

    return ;
}