[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 ;
}