終于認識了什么叫做期望。。

這道題題目挺長的哈，看上去又是期望又是圖論的樣子。

但是圖論方面只需要做個預(yù)處理，然后就可以用dp弄進答案。

在教室之間移動，有腦子的都不會走彎路更累吧，所以最短路走一波。

然后就是dp的事情了。

設(shè)\(dp[i][j][0/1]\)是第\(i\)個時間段，從開始到現(xiàn)在（包含現(xiàn)在）已經(jīng)申請了\(j\)次，要去往原教室（0）或新教室（1）上課的期望。

這道題的第一次去上課的路徑是白送你的，具體看樣例的解釋就知道了。

如何算期望？一般使用全期望公式，就是各種情況的概率乘以相應(yīng)的值的和，類似于加權(quán)平均數(shù)的算法。

所以考慮一下狀態(tài)轉(zhuǎn)移方程：

這些東西的轉(zhuǎn)移都可能來自上次換了或者上次沒換。

然后重點來了：上次沒換這種情況還要分為兩種：換了成功了或者換了但沒成功。對于這些情況，算期望的時候要全部都考慮在內(nèi)，然后算進去，才是正確的答案。

\(dp[i][j][0]\)可能由上次沒換得來，直接在原來的狀態(tài)基礎(chǔ)上加上這段路徑即可。

但也可能由上次換了得來，設(shè)上次換成功的概率為\(k\)，則我們應(yīng)該加上\(k \times G[s_1][t_0] + (1 - k) \times G[s_0][t_0]\)。

\(dp[i][j][1]\)就復(fù)雜了。

先考慮由上次不換轉(zhuǎn)移來。同理應(yīng)該在原來的基礎(chǔ)上加上\(k \times G[s_0][t_1] + (1 - k) \times G[s_0][t_0]\)，這里的\(k\)是當(dāng)前成功的概率。

如果是上次不換，由乘法原理，就會有4種情況，講道理自己推一下，并不難，但太長。

細節(jié)方面可以預(yù)處理一波邊界問題，不然可能遞推的時候很難受。

代碼：

#include<cstdio> #include<cstring> #include<algorithm> const int maxn = 2005, maxv = 305; const double INF = 999999999; int c[maxn][2]; double p[maxn], dp[maxn][maxn][2]; int G[maxn][maxn]; int n, m, v, e;int main() {scanf("%d%d%d%d", &n, &m, &v, &e);for(int i = 1; i <= n; i++) scanf("%d", &c[i][0]);for(int i = 1; i <= n; i++) scanf("%d", &c[i][1]);for(int i = 1; i <= n; i++) scanf("%lf", &p[i]);memset(G, 0x3f, sizeof G);for(int i = 1; i <= v; i++) G[i][i] = 0;while(e--){int u, v, w; scanf("%d%d%d", &u, &v, &w);G[u][v] = G[v][u] = std::min(G[u][v], w);}for(int k = 1; k <= v; k++)for(int i = 1; i <= v; i++)for(int j = 1; j <= v; j++)G[i][j] = std::min(G[i][j], G[i][k] + G[k][j]);for(int i = 1; i <= n; i++)for(int j = 0; j <= m; j++)dp[i][j][0] = dp[i][j][1] = INF;dp[1][0][0] = dp[1][1][1] = dp[1][1][0] = 0;for(int i = 2; i <= n; i++) dp[i][0][0] = dp[i - 1][0][0] + G[c[i - 1][0]][c[i][0]];for(int i = 2; i <= n; i++){int s0 = c[i - 1][0], s1 = c[i - 1][1];int t0 = c[i][0], t1 = c[i][1];for(int j = 1; j <= std::min(i, m); j++){dp[i][j][0] = std::min(dp[i][j][0], std::min(dp[i - 1][j][0] + G[s0][t0], dp[i - 1][j][1] + p[i - 1] * G[s1][t0] + (1 - p[i - 1]) * G[s0][t0]));dp[i][j][1] = std::min(dp[i][j][1], std::min(dp[i - 1][j - 1][0] + p[i] * G[s0][t1] + (1 - p[i]) * G[s0][t0], dp[i - 1][j - 1][1] + p[i - 1] * p[i] * G[s1][t1] + p[i - 1] * (1 - p[i]) * G[s1][t0] + (1 - p[i - 1]) * p[i] * G[s0][t1] + (1 - p[i - 1]) * (1 - p[i]) * G[s0][t0]));}}double ans = INF;for(int i = 0; i <= m; i++) ans = std::min(ans, std::min(dp[n][i][0], dp[n][i][1]));printf("%.2lf\n", ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Garen-Wang/p/9556900.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的P1850 换教室的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。