---

題目傳送門

---

前言

終于自己想出概率期望 $dp$ 的狀態了，但是依舊沒能相對轉移方程。（招笑）

---

暴力

這題部分分和特殊情況分給的挺多的，所以先拿部分分。

一、思路

1. 先跑一邊 $Floyd$ 最短路求出兩點間最短距離 $di{s}_{i,j}$。
2. 對于 $m=0$，答案就是 ${\sum }_{i=1}^{n?1}di{s}_{c_i,c_{i+1}}$；
   對于所有 $n\le 20$，直接用狀態壓縮，二進制枚舉所有 【申請情況】 與 【同意情況】（注意：這兩者不一樣，因為申請了不一定同意，所以枚舉申請情況之下還要枚舉同意情況），直接計算。

二、復雜度

1. 空間：$O(v^2+n)$。
2. 時間：對于 $m=0$，$O(v^3+n)$；對于 $n\le 20$，$O(v^3+n\times 2^n\times 2^m)$。
   （當然后者的時間復雜度遠遠跑不滿，因為對于多數數據 $m$ 很小，會限制枚舉的狀態數量）

三、代碼

#include <bits/stdc++.h>using namespace std;const int maxn = 2e3 + 7;
const int maxv = 3e2 + 7;
const int inf  = 0x3f3f3f3f;int n, m, v, e;
int c[maxn], d[maxn];
double p[maxn];
int dis[maxv][maxv];
void Floyd() {for (int k = 1; k <= v; ++k)for (int i = 1; i <= v; ++i)for (int j = 1; j <= v; ++j)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
double ans;
int main() {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);memset(dis, inf, sizeof(dis));for (int i = 1; i <= v; ++i) dis[i][i] = dis[0][i] = dis[i][0] = 0;for (int i = 1, a, b, w; i <= e; ++i) {scanf("%d%d%d", &a, &b, &w);dis[a][b] = dis[b][a] = min(w, dis[a][b]);}Floyd();if (m == 0) {for (int i = 1; i < n; ++i)ans += dis[c[i]][c[i + 1]];printf("%.2lf\n", ans);return 0;}ans = 2e9;for (int s = 0; s < (1 << n); ++s) {  // 枚舉【申請情況】if (__builtin_popcount(s) > m) continue;  // 用來計算 s 二進制中有多少個 1 的函數double sum = 0;  // 此【申請情況】下的期望for (int ss = s; 1; ss = s & (ss - 1)) {  // 枚舉【同意情況】double tmp = 0;  // 此【同意情況】對【申請情況】的貢獻for (int i = 2; i <= n; ++i) {int lst = ((ss & (1 << (i - 1 - 1))) ? d[i - 1] : c[i - 1]);int now = ((ss & (1 << (i - 1))) ? d[i] : c[i]);tmp += dis[lst][now];}for (int i = 1; i <= n; ++i)if (ss & (1 << (i - 1))) tmp *= p[i];else if (s & (1 << (i - 1))) tmp *= 1 - p[i];sum += tmp;if (ss == 0) break;}ans = min(ans, sum);}printf("%.2lf\n", ans);return 0;
} 

期望得分 $68pts$，實際得分 $68pts$。
（洛谷測評機跑出來挺迷的，應該是數據水的問題，前面暴力的數據點一部分沒過，后面正解的數據點過了一部分）

---

正解

概率期望的題一般就是拿 $dp$ 做。

一、思路

狀態設計

• 很明顯要有兩維的狀態 $i,j$，表示前 $i$ 個中選了 $j$ 個。
  但是由于花費還與上一狀態有關（上一個課程是在 $c_i$ 還是 $d_i$），所以還要一維表示這個課是否被申請了。
• 設 $d{p}_{i,j,0/1}$ 表示在前 $i$ 個課中 申請了（注意不是同意！！）$j$ 個，且第 $i$ 個課【沒被申請 / 被申請了】時的最小期望。

狀態轉移

1. 若當前課程 $i$ 不申請，且上一個課程也沒有申請，那么轉移方程為：$$d{p}_{i,j,0}=min(d{p}_{i,j},d{p}_{i?1,j,0}+di{s}_{c_{i?1},c_i})$$
2. 若當前課程 $i$ 不申請，但上一個課程申請了，那么轉移方程為（轉移條件為 $j>0$）：$$d{p}_{i,j,0}=min(d{p}_{i,j,0},d{p}_{i?1,j,1}+di{s}_{c_{i?1},c_i}\times (1?k_i)+di{s}_{d_{i?1},c_i}\times k_i)$$后面的分別對應【上一次申請沒通過】和【上一次申請通過了】；
3. 若當前課程 $i$ 申請，那么上一次可以申請，也可以不申請，總共有四種情況，在此就不列舉出來了（條件當然也是 $j>0$）。

邊界條件

• 只有一個課程時，申請或不申請期望花費都為 $0$，即：$d{p}_{1,0,0}=d{p}_{1,1,1}=0$。
• 而對于 $d{p}_{1,0,1},d{p}_{1,1,0}$ 這種不合法狀態，我們可以先把他們設為正無窮，這樣就不會從它門轉移了。

答案

• 因為題目說可以不用玩 $m$ 次申請，所以答案就是 m i n i = 0 m { d p n , i , 0 , d p n , i , 1 } min_{i = 0}^{m} \left\{dp_{n, i,0}, dp_{n, i, 1} \right\} mini=0m?{dpn,i,0?,dpn,i,1?}。

復雜度

1. 空間：$O(v^2+n\times m)$；
2. 時間：$O(v^3+n\times m)$。

二、代碼

#include <bits/stdc++.h>using namespace std;const int maxn = 2e3 + 7;
const int maxv = 3e2 + 7;
const int inf  = 0x3f3f3f3f;int n, m, v, e;
int c[maxn], d[maxn];
double p[maxn];
int dis[maxv][maxv];
void Floyd() {for (int k = 1; k <= v; ++k)for (int i = 1; i <= v; ++i)for (int j = 1; j <= v; ++j)dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}double dp[maxn][maxn][2];
double ans;
int main() {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);memset(dis, 63, sizeof(dis));for (int i = 1; i <= v; ++i) dis[i][i] = dis[i][0] = dis[0][i] = 0;for (int i = 1, a, b, w; i <= e; ++i) {scanf("%d%d%d", &a, &b, &w);dis[a][b] = dis[b][a] = min(w, dis[a][b]);}Floyd();for (int i = 0; i <= n; ++i)for (int j = 0; j <= m; ++j)dp[i][j][0] = dp[i][j][1] = 2e9;dp[1][0][0] = dp[1][1][1] = 0;for (int i = 2; i <= n; ++i) {dp[i][0][0] = dp[i - 1][0][0] + dis[c[i - 1]][c[i]];for (int j = 1; j <= min(i, m); ++j) {// 巨丑馬蜂dp[i][j][0] = min(dp[i - 1][j][0] + dis[c[i - 1]][c[i]],dp[i - 1][j][1] + dis[c[i - 1]][c[i]] * (1 - p[i - 1]) + dis[d[i - 1]][c[i]] * p[i - 1]);dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + dis[c[i - 1]][c[i]] * (1 - p[i]) + dis[c[i - 1]][d[i]] * p[i]);dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + dis[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]) + dis[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] + dis[d[i - 1]][c[i]] * p[i - 1] * (1 - p[i]) + dis[d[i - 1]][d[i]] * p[i - 1] * p[i]);}}ans = 2e9;for (int i = 0; i <= m; ++i)ans = min(ans, min(dp[n][i][0], dp[n][i][1]));printf("%.2lf\n", ans);return 0;
} 

期望的分 $100pts$，實際得分 $100pts$。