題目描述

對(duì)于剛上大學(xué)的牛牛來(lái)說(shuō), 他面臨的第一個(gè)問題是如何根據(jù)實(shí)際情況中情合適的課程。

在可以選擇的課程中,有2n節(jié)課程安排在n個(gè)時(shí)間段上。在第 i ( 1≤ i≤n)個(gè)時(shí)同段上, 兩節(jié)內(nèi)容相同的課程同時(shí)在不同的地點(diǎn)進(jìn)行, 其中, 牛牛預(yù)先被安排在教室 ci上課, 而另一節(jié)課程在教室 di進(jìn)行。

在不提交任何申請(qǐng)的情況下,學(xué)生們需要按時(shí)間段的順序依次完成所有的n節(jié)安排好的課程。如果學(xué)生想更換第i節(jié)課程的教室,則需要提出中情。若申請(qǐng)通過,學(xué)生就可以在第 i個(gè)時(shí)間段去教室 di上課, 否則仍然在教室 ci上課。

由于更換教室的需求太多, 申請(qǐng)不一定能獲得通過。 通過計(jì)算, 牛牛發(fā)現(xiàn)申請(qǐng)更換第 i節(jié)課程的教室時(shí), 中情被通過的概率是一個(gè)已知的實(shí)數(shù) ki, 并且對(duì)于不同課程的申請(qǐng), 被通過的概率是互相獨(dú)立的。

學(xué)校規(guī)定, 所有的申請(qǐng)只能在學(xué)期開始前一次性提交, 并且每個(gè)人只能選擇至多m節(jié)課程進(jìn)行申請(qǐng)。 這意味著牛牛必須一次性決定是否申請(qǐng)更換每節(jié)課的教室, 而不能根據(jù)某些課程的申請(qǐng)結(jié)果來(lái)決定其他課程是否申請(qǐng); 牛牛可以申請(qǐng)白己最希望更換教室的 m門課程,也可以不用完這m個(gè)中情的機(jī)會(huì),甚至可以一門課程都不申請(qǐng)。

因?yàn)椴煌恼n程可能會(huì)被安排在不同的教室進(jìn)行, 所以牛牛需要利用課問時(shí)間從一間教室趕到另一間教室。

牛牛所在的大學(xué)有 v個(gè)教室,有 e條道路。每條道路連接兩間教室, 并且是可以雙向通行的。 由于道路的長(zhǎng)度和擁;i者程度不同, 通過不同的道路耗費(fèi)的體力可能會(huì)有所不同。當(dāng)?shù)趇 ( 1≤i≤n-1 )節(jié)課結(jié)束后,牛牛就會(huì)從這節(jié)課的教室出發(fā),選擇一條耗費(fèi)體力最少的路徑前往下一節(jié)課的教室。

現(xiàn)在牛牛想知道,申請(qǐng)哪幾門課程可以使他因在教室問移動(dòng)耗費(fèi)的體力值的總和的期望值最小,請(qǐng)你幫他求出這個(gè)最小值。

輸入輸出格式

輸入格式：

?

第一行四個(gè)整數(shù) n,m,v,e 。 n表示這個(gè)學(xué)期內(nèi)的時(shí)間段的數(shù)量; m表示牛牛最多可以申請(qǐng)更換多少節(jié)課程的教室; v表示牛牛學(xué)校里教室的數(shù)量; e表示牛牛的學(xué)校里道路的數(shù)量。

第二行n個(gè)正整數(shù),第 i ( 1≤ i≤ n)個(gè)正整數(shù)表示c,,即第 i個(gè)時(shí)間段牛牛被安排上課的教室;保證1≤ ci≤ v。

第三行n個(gè)正整數(shù),第 i ( 1≤ i≤ n)個(gè)正整數(shù)表示di,即第 i個(gè)時(shí)間段另一間上同樣課程的教室;保證1≤ di≤ v。

第四行n個(gè)實(shí)數(shù),第 i ( 1≤ i≤ n)個(gè)實(shí)數(shù)表示ki,即牛牛申請(qǐng)?jiān)诘?i個(gè)時(shí)間段更換教室獲得通過的概率。保證0≤ ki≤1 。

接下來(lái) e行,每行三個(gè)正整數(shù)aj,bj,wj,表示有一條雙向道路連接教室 aj ,bj ,通過這條道路需要耗費(fèi)的體力值是 Wj ;保證1≤ aj,bj≤ v, 1≤ wj≤100 。

保證1≤n≤2000, 0≤m≤2000, 1≤v≤300, 0≤ e≤90000。

保證通過學(xué)校里的道路,從任何一間教室出發(fā),都能到達(dá)其他所有的教室。

保證輸入的實(shí)數(shù)最多包含3位小數(shù)。

?

輸出格式：

?

輸出一行,包含一個(gè)實(shí)數(shù),四舎五入精確到小數(shù)點(diǎn)后恰好2位,表示答案。你的

輸出必須和標(biāo)準(zhǔn)輸出完全一樣才算正確。

測(cè)試數(shù)據(jù)保證四舎五入后的答案和準(zhǔn)確答案的差的絕對(duì)值不大于4 *10^-3 。 (如果你不知道什么是浮點(diǎn)誤差, 這段話可以理解為: 對(duì)于大多數(shù)的算法, 你可以正常地使用浮點(diǎn)數(shù)類型而不用對(duì)它進(jìn)行特殊的處理)

?

輸入輸出樣例

輸入樣例#1：
3 2 3 3 2 1 2 1 2 1 0.8 0.2 0.5 1 2 5 1 3 3 2 3 1 輸出樣例#1：
2.80

說(shuō)明

【樣例1說(shuō)明】

所有可行的申請(qǐng)方案和期望收益如下表:

【提示】

道路中可能會(huì)有多條雙向道路連接相同的兩間教室。 也有可能有道路兩端連接

的是同一間教室。

2.請(qǐng)注意區(qū)分n,m,v,e的意義, n不是教室的數(shù)量, m不是道路的數(shù)量。

特殊性質(zhì)1:圖上任意兩點(diǎn) ai, bi, ai≠ bi間,存在一條耗費(fèi)體力最少的路徑只包含一條道路。

特殊性質(zhì)2:對(duì)于所有的1≤ i≤ n， ki= 1 。

分析：一開始不懂期望的概念，現(xiàn)在大致可以理解為一個(gè)事件發(fā)生的概率*這個(gè)事件的權(quán)值，理解了概念，就比較容易做了。一開始可以想到爆搜，即每個(gè)時(shí)間段到底提不提交申請(qǐng)，這樣的話會(huì)TLE.其實(shí)可以用dp,設(shè)dp[i][j][0]為前i個(gè)時(shí)間段已經(jīng)提交了j個(gè)申請(qǐng)，第i個(gè)時(shí)間段不提交申請(qǐng)的最小期望值，dp[i][j][1]為前i個(gè)時(shí)間段已經(jīng)提交了j個(gè)申請(qǐng)，第i個(gè)時(shí)間段提交申請(qǐng)的最小期望值。那么dp[i][j][0] = min(dp[i - 1][j][0] + map[c[i - 1]][c[i]], dp[i - 1][j][1] + map[d[i - 1]][c[i]] * k[i - 1] + map[c[i - 1]][c[i]] * (1.0 - k[i - 1]))，我們可以這么理解：如果第i-1個(gè)時(shí)間段不提交，直接從原本的i-1個(gè)教室走到第i個(gè)教室，如果第i-1個(gè)時(shí)間段提交申請(qǐng)的話，那么有k[i-1]的概率能夠更換到教室，還有1 - k[i-1]的概率不能換到教室，根據(jù)期望值可以相加的性質(zhì)，就能求出來(lái)。然后可以發(fā)現(xiàn)dp[i][j][1]的處理是類似的 dp[i][j][1] = min(dp[i][j][1],min(dp[i - 1][j - 1][0] + map[c[i - 1]][d[i]] * k[i] + map[c[i - 1]][c[i]] * (1.0 - k[i]), dp[i - 1][j - 1][1] + map[c[i - 1]][c[i]] * (1.0 - k[i - 1]) * (1.0 - k[i]) + map[c[i - 1]][d[i]] * (1.0 - k[i - 1]) * k[i] + map[d[i - 1]][c[i]] * k[i - 1] * (1 - k[i]) + map[d[i - 1]][d[i]] * k[i - 1] * k[i])).

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <string>using namespace std;int n, m, v, e, c[2010], d[2010], map[310][310]; double dp[2010][2010][2]; double k[2010],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", &k[i]);for (int i = 1; i <= v; i++)for (int j = 1; j <= v; j++)if (i != j)map[i][j] = 1000000000;for (int i = 1; i <= e; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);map[a][b] = min(map[a][b], w);map[b][a] = map[a][b];}//floydfor (int k = 1; k <= v; k++)for (int i = 1; i <= v; i++)for (int j = 1; j <= v; j++)if (map[i][k] + map[k][j] < map[i][j])map[i][j] = map[i][k] + map[k][j];for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++)dp[i][j][0] = dp[i][j][1] = 1e30;dp[1][0][0] = dp[1][1][1] = 0;for (int i = 2; i <= n; i++)for (int j = 0; j <= m; j++){dp[i][j][0] = min(dp[i - 1][j][0] + map[c[i - 1]][c[i]], dp[i][j][0]);if (j >= 1){dp[i][j][0] = min(dp[i - 1][j][0] + map[c[i - 1]][c[i]], dp[i - 1][j][1] + map[d[i - 1]][c[i]] * k[i - 1] + map[c[i - 1]][c[i]] * (1.0 - k[i - 1]));dp[i][j][1] = min(dp[i][j][1],min(dp[i - 1][j - 1][0] + map[c[i - 1]][d[i]] * k[i] + map[c[i - 1]][c[i]] * (1.0 - k[i]), dp[i - 1][j - 1][1] + map[c[i - 1]][c[i]] * (1.0 - k[i - 1]) * (1.0 - k[i]) + map[c[i - 1]][d[i]] * (1.0 - k[i - 1]) * k[i] + map[d[i - 1]][c[i]] * k[i - 1] * (1 - k[i]) + map[d[i - 1]][d[i]] * k[i - 1] * k[i]));}}ans = 1e30;for (int i = 0; i <= m; i++)ans = min(ans, min(dp[n][i][1], dp[n][i][0]));printf("%.2lf", ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/7253064.html

總結(jié)

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

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