题解：P1850 [NOIP 2016 提高组] 换教室

题目

在一个有 个点 条边的图上，你要完成图上移动任务，并最小化代价。

任务有 个阶段，每个阶段有两个点，。原则上你每次从 ，代价就是路径长度。但是现在你有 次改变命运的申请机会。你可以对每个阶段申请一次改变目的地 为 ，申请成功的概率是 。

请问在所有的申请策略中，代价的最小期望是多少？

题解

状态的设置前两维比较经典：阶段，额度。但是第三维是这道题的特殊的地方。但是也很好想到，因为这个和转移有关。想象自己写 ，对于上一个点有没有申请，成没成功，当前点有没有申请，成没成功，都是转移的时候乘 相关项的重要讨论，所以是要记录在状态中的。

状态转移方程就是大的分类讨论：

• 当前点不做申请；
  • 上个点不做申请；
  • 上个点要做申请；
    • 上个点成功了；
    • 上个点没成功；
• 当前点要做申请；
  • 上个点不做申请；
    • 当前点成功了；
    • 当前点没成功；
  • 上个点要做申请；
    • 上个点成功了；
      • 当前点成功了；
      • 当前点没成功；
    • 上个点没成功；
      • 当前点成功了；
      • 当前点没成功；

这个题目细节比较多，主要集中在三个位置：

1. 输入，经典的邻接矩阵 + 的坑点就是重边，注意取 ；
2. DP 初始化，我们要求最小，所以就要赋极大值，而且申请 次的时候也是需要初始化的，因为那个情况也只能从更早的阶段推过去，不可以遗漏；
   （我才不会告诉你们我 WA 在这里了）
3. 状态转移方程，比较复杂，经典的解决方法就是局部变量 + 代码对齐；

代码如下：

#include<bits/stdc++.h>
#define dwb double

using namespace std;

const int MAXN = 2005;
const int MAXV = 305;
const dwb INF = 1e9 + 7;

int n, m, v, e;
int dis[MAXV][MAXV];
int c[MAXN], d[MAXN];
dwb p[MAXN];
dwb f[MAXN][MAXN][2];

int main() {
    /*===IO Stream===*/
    memset(dis, 0x3f, sizeof(dis));
    scanf("%d%d%d%d", &n, &m, &v, &e);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &c[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &d[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= e; ++i) {
        int from, to, weight;
        scanf("%d%d%d", &from, &to, &weight);
        dis[from][to] = min(dis[from][to], weight);
        dis[to][from] = min(dis[to][from], weight);
    }
    /*===Pink Floyd===*/
    for (int i = 1; i <= v; ++i)
        for (int j = 1; j <= v; ++j)
            for (int k = 1; k <= v; ++k)
                dis[j][k] = min(dis[j][k], dis[i][j] + dis[i][k]);
    for (int i = 1; i <= v; ++i)
        dis[i][i] = 0;
    /*===Dynamic Programming===*/

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            f[i][j][0] = INF;
            f[i][j][1] = INF;
        }

    f[1][0][0] = 0;
    f[1][1][1] = 0;
    for (int i = 2; i <= n; ++i) {
        dwb disCC = dis[c[i - 1]][c[i]];
        dwb disCD = dis[c[i - 1]][d[i]];
        dwb disDC = dis[d[i - 1]][c[i]];
        dwb disDD = dis[d[i - 1]][d[i]];

        f[i][0][0] = f[i - 1][0][0] + disCC;

        for (int j = 1; j <= min(i, m); ++j) {
            f[i][j][0] = min(f[i][j][0], f[i - 1][j][0]
                             + disCC);
            f[i][j][0] = min(f[i][j][0], f[i - 1][j][1]
                             + disDC * p[i - 1] + disCC * (1 - p[i - 1]));

            f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][0]
                             + disCC * (1 - p[i]) + disCD * p[i]);
            f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][1]
                             + disCC * (1 - p[i - 1]) * (1 - p[i])
                             + disCD * (1 - p[i - 1]) * p[i]
                             + disDC * p[i - 1] * (1 - p[i])
                             + disDD * p[i - 1] * p[i]);
        }
    }

    dwb ans = INF;
    for (int i = 0; i <= m; ++i)
        ans = min({ans, f[n][i][0], f[n][i][1]});
    printf("%.2lf", ans);

    return 0;
}