4720: [Noip2016]換教室

Description

對于剛上大學(xué)的牛牛來說,他面臨的第一個問題是如何根據(jù)實際情況申請合適的課程。在可以選擇的課程中,有2n節(jié)課程安排在n個時間段上。在第i(1≤i≤n)個時間段上,兩節(jié)內(nèi)容相同的課程同時在不同的地點進行,其中,牛牛預(yù)先被安排在教室ci上課,而另一節(jié)課程在教室di進行。在不提交任何申請的情況下,學(xué)生們需要按時間段的順序依次完成所有的n節(jié)安排好的課程。如果學(xué)生想更換第i節(jié)課程的教室,則需要提出申請。若申請通過,學(xué)生就可以在第i個時間段去教室di上課,否則仍然在教室ci上課。由于更換教室的需求太多,申請不一定能獲得通過。通過計算,牛牛發(fā)現(xiàn)申請更換第i節(jié)課程的教室時,申請被通過的概率是一個已知的實數(shù)ki,并且對于不同課程的申請,被通過的概率是互相獨立的。學(xué)校規(guī)定,所有的申請只能在學(xué)期開始前一次性提交,并且每個人只能選擇至多m節(jié)課程進行申請。這意味著牛牛必須一次性決定是否申請更換每節(jié)課的教室,而不能根據(jù)某些課程的申請結(jié)果來決定其他課程是否申請;牛牛可以申請自己最希望更換教室的m門課程,也可以不用完這m個申請的機會,甚至可以一門課程都不申請。因為不同的課程可能會被安排在不同的教室進行,所以牛牛需要利用課間時間從一間教室趕到另一間教室。牛牛所在的大學(xué)有v個教室,有e條道路。每條道路連接兩間教室,并且是可以雙向通行的。由于道路的長度和擁堵程度不同,通過不同的道路耗費的體力可能會有所不同。當(dāng)?shù)趇(1≤i≤n-1)節(jié)課結(jié)束后,牛牛就會從這節(jié)課的教室出發(fā),選擇一條耗費體力最少的路徑前往下一節(jié)課的教室。現(xiàn)在牛牛想知道,申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的期望值最小,請你幫他求出這個最小值。

Input

第一行四個整數(shù)n,m,v,e。n表示這個學(xué)期內(nèi)的時間段的數(shù)量;m表示牛牛最多可以申請更換多少節(jié)課程的教室; v表示牛牛學(xué)校里教室的數(shù)量;e表示牛牛的學(xué)校里道路的數(shù)量。 第二行n個正整數(shù),第i(1≤i≤n)個正整數(shù)表示c,,即第i個時間段牛牛被安排上課的教室;保證1≤ci≤v。 第三行n個正整數(shù),第i(1≤i≤n)個正整數(shù)表示di,即第i個時間段另一間上同樣課程的教室;保證1≤di≤v。 第四行n個實數(shù),第i(1≤i≤n)個實數(shù)表示ki,即牛牛申請在第i個時間段更換教室獲得通過的概率。保證0≤ki≤1。 接下來e行,每行三個正整數(shù)aj,bj,wj,表示有一條雙向道路連接教室aj,bj,通過這條道路需要耗費的體力值是Wj; 保證1≤aj,bj≤v,1≤wj≤100。 保證1≤n≤2000,0≤m≤2000,1≤v≤300,0≤e≤90000。 保證通過學(xué)校里的道路,從任何一間教室出發(fā),都能到達其他所有的教室。 保證輸入的實數(shù)最多包含3位小數(shù)。

Output

輸出一行,包含一個實數(shù),四舎五入精確到小數(shù)點后恰好2位,表示答案。你的 輸出必須和標準輸出完全一樣才算正確。 測試數(shù)據(jù)保證四舎五入后的答案和準確答案的差的絕對值不大于4*10^-3。(如果你不知道什么是浮點誤差,這段話可以理解為:對于大多數(shù)的算法,你可以正常地使用浮點數(shù)類型而不用對它進行特殊的處理)

Sample Input

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

Sample Output

2.80

---

　　這道題也可以算得上是經(jīng)典了。當(dāng)時考NOIP碰到這道題，當(dāng)時還壯志滿懷，很長的一道題（至少當(dāng)時看來是這樣的）很快就被我讀完了，發(fā)現(xiàn)可以分成三份：課程、教室，申請、概率，道路、耗費體力最少。 　　當(dāng)時，我的很多同學(xué)見此題太長，就根本沒有看。此題雖然沾期望，但其實很簡單。 ----------因為后面扯的東西比較多，就在這里講一下思路。---------- 　　我們這樣開數(shù)組：f[2][2][M]，第一維枚舉課程但可以“滾動”(cur)，第二位判斷在第i門課程是否提交申請，第三維給現(xiàn)在已申請的課程計一下數(shù)。空間是O（M）的，時間是O（NM）的，最后輸出f[cur][j][p](j=0,1; p=0,1,...,m) 　　這樣，我們可以考慮轉(zhuǎn)移。一個課程如果沒有申請，那就是100%的“純爺們兒”教室c。但如果申請了呢？可以YY一下薛定諤的貓，有概率的事件可以當(dāng)做對立統(tǒng)一的個體。也就是說一個課程如果申請了，就可以看做k[i]個d教室和1-k[i]個c教室，實際轉(zhuǎn)移時思考一下即可。 　　關(guān)于方程可以看看我的代碼（本文末尾）。 ----------好的，思路講完了。我可以開始扯了。---------- 　　當(dāng)時我高興極了，發(fā)現(xiàn)可以把課程當(dāng)做i，把申請數(shù)當(dāng)做j，把此時是否申請當(dāng)0/1。當(dāng)時才學(xué)了DP，只會背包（還是最簡單的）和floyd，什么LIS、數(shù)位、狀壓（NOIPD2T3ANGRYBIRD）、樹形都不知道，更不用說什么概率和期望了……然而就是考了。YJQ表示，不要再逼我吃鍵盤了。 　　關(guān)于吃鍵盤一事，都是因為——YJQ說NOIP絕對不考期望DPNOIP這么水的考試怎么可能考這種東西寫個暴力就A題的比賽要是考了這種東西我就直播吃鍵盤……YJQ其實是一個很謹慎的人，不像lemonoil每天立下flag要直播吃掉∞個鍵盤。 “兜售巧克力味鍵盤了喂！專門為立flag死掉的人設(shè)計的喂~~~” 　　所以就是這樣的。然而我當(dāng)時就是想到了如何去做，雖然現(xiàn)在看完題就可以切過去。因為當(dāng)時我既會背包，也會floyd。不過，天有不測風(fēng)云，我當(dāng)時的代碼實現(xiàn)能力實在是太弱了……
　　弱到什么地步？也就是說，我發(fā)現(xiàn)當(dāng)時k數(shù)組定義的是int類型……也許，質(zhì)問當(dāng)時的我，我還會義憤填膺地說，int不就是數(shù)么整數(shù)是數(shù)小數(shù)難道不是數(shù)么？！ 　　呃呃呃呃呃。 　　然而，當(dāng)我現(xiàn)在做到這道題時，當(dāng)我已經(jīng)“掌握”了概率與期望的時候，還是WA。 　　恩。請來客忽略我的強制調(diào)劑（eyeprotect）。一邊調(diào)，一會兒AC，一會兒又WA的體驗真的是第一回碰到。更令人驚奇的是，中間居然還有CE，讓人頗為尷尬。要是NOIP也這樣，那恐怕就只有再見OI了。 　　最后突然發(fā)現(xiàn)，卡了這么久竟是這兩個原因。 　　1.memset(dis,65,sizeof(dis))很明顯是錯的，因為在floyd內(nèi)部，dis+dis會跳負。應(yīng)將65改成63或127/2。 　　2.這個地方才真正調(diào)了我很久，這個地方是讓人非常尷尬的。DP中常常有x=std::min(x,y);的語句出現(xiàn)，但我在修改時只把第一個x改對了……所以說需要有#define smin(x,y) x=std::min(x,y)啊（YYF、mcfx等大佬強力推薦）！ 　　最后掛一波代碼吧。 1 /************************************************************** 2 Problem: 4720 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1960 ms 7 Memory:1292 kb 8 ****************************************************************/ 9 10 #define PN "classroom" 11 #include <cstdio> 12 #include <cstring> 13 #include <algorithm> 14 #define smin(x,y) x=std::min(x,y) 15 const int N = 2000+50; 16 const int M = 2000+50; 17 const int V = 300+10; 18 int n, m, v, e, c[N], d[N], dis[V][V], cur=0; 19 double k[N], f[2][2][M]; 20 21 int main() { 22 scanf("%d%d%d%d",&n,&m,&v,&e); 23 for( int i = 1; i <= n; i++ ) scanf("%d",&c[i]); 24 for( int i = 1; i <= n; i++ ) scanf("%d",&d[i]); 25 for( int i = 1; i <= n; i++ ) scanf("%lf",&k[i]); 26 memset(dis,63,sizeof(dis)); 27 for( int i = 1,a,b,w; i <= e; i++ ) { 28 scanf("%d%d%d",&a,&b,&w); 29 if(dis[a][b]>w) dis[a][b]=dis[b][a]=w; 30 } 31 for( int i = 1; i <= v; i++ ) dis[i][i]=0; 32 for( int p = 1; p <= v; p++ ) 33 for( int i = 1; i <= v; i++ ) 34 for( int j = 1; j <= v; j++ ) 35 if (dis[i][j]>dis[i][p]+dis[p][j]) 36 dis[i][j]=dis[i][p]+dis[p][j], 37 dis[j][i]=dis[i][j]; 38 memset(f[cur],127,sizeof(f[cur]));f[cur][0][0]=f[cur][1][1]=0; 39 for( int i = 2; i <= n; i++ ) { 40 cur^=1;memset(f[cur],127,sizeof(f[cur])); 41 for( int p = 0; p <= m; p++ ) { 42 smin(f[cur][0][p],f[cur^1][1][p]+k[i-1]*dis[c[i]][d[i-1]]+(1-k[i-1])*dis[c[i]][c[i-1]]); 43 smin(f[cur][0][p],f[cur^1][0][p]+dis[c[i]][c[i-1]]); 44 smin(f[cur][1][p+1],f[cur^1][1][p]+k[i]*k[i-1]*dis[d[i]][d[i-1]]+(1-k[i])*k[i-1]*dis[c[i]][d[i-1]]+k[i]*(1-k[i-1])*dis[d[i]][c[i-1]]+(1-k[i])*(1-k[i-1])*dis[c[i]][c[i-1]]); 45 smin(f[cur][1][p+1],f[cur^1][0][p]+k[i]*dis[d[i]][c[i-1]]+(1-k[i])*dis[c[i]][c[i-1]]); 46 } 47 } 48 double ans=2000000000; 49 for( int j = 0; j <= 1; j++ ) 50 for( int p = 0; p <= m; p++ ) 51 ans=std::min(ans,f[cur][j][p]); 52 printf("%.2lf\n",ans); 53 return 0; 54 } 55 NOIP第一道期望DP

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

總結(jié)

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

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