NOIP 2018【摆渡车】题解
updated on 2018.11.17：
1. 之前所說的最后一項優化經檢驗發現有\(bug\)，已經去掉；
2. 對文中的一些錯誤進行了修改，同時對文章的行文作了一些調整，便于大家理解。
建議大家在博客里食用：傳送門
要是PJ組再考這么難的DP，我就當官把CCF取締了
開個玩笑。
此題正解：\(\mathrm{DP}\)+各種剪枝 or 優化
一、引理
對于每個乘客，能搭載ta的車的發車時間只有\(m\)種情況；
設這個乘客開始等候的時間是\(t_i\)，則對應的\(m\)種情況是\([t_i,t_i+m)\)（方括號 和 圓括號 表示左閉右開區間）。
證明
如果存在一種情況，其發車時間是\(\geqslant t_i+m\)的，則由題意可知，發車時間可以提早若干輪（也就是減去若干個\(m\)）到達\([t_i,t_i+m)\)這個區間，這樣做不會影響發車時間\(\geqslant t+m\)的那趟車，不會有后效性。
如果\(<m\)的話，那這個乘客根本就坐不上這趟車，所以不需要考慮。
二、基本思想
首先，題目給定我們的這\(n\)個人開始等候的時間是亂的，所以我們要先按照開始等車的時間把這\(n\)個人排個序。
設\(f[i][j]\)表示用擺渡車已經載了前\(i\)個人，且搭載了第\(i\)個人（不一定只搭載第\(i\)個人）的那趟擺渡車的發車時間是（\(t_i+j\)）的最小等候時間和。（\(t_i\)的意義與題意相同）
這里要注意：\(t_i+j\)同時還需要滿足\(t_i+j<t_{i+1}\)
因為如果\(\geqslant t_{i+1}\)，那這趟車就可以把第\(i+1\)個人也搭上了，違反了\(\mathrm{DP}\)狀態的定義。對于每個\(f[i][j]\)，枚舉上一趟擺渡車的出發時間。
等等！數據范圍寫著：
\[1 \leqslant t_i \leqslant 4\times10^6 \]
你跟我說枚舉時間？你這最起碼都\(O(n*t_i) \sim O(2\times10^9)\) 的時間復雜度了，怎么\(AC\)？
別著急啊，我還沒說完呢。
其實引理已經告訴我們，我們不需要把整個\(t_i\)枚舉完。
由引理可得，對于前\(i-1\)個乘客，每個乘客能搭載的擺渡車的發車時間只有\(m\)種情況，所以我們只需要枚舉這\((i-1)\times m\)種情況即可。其他情況都是廢的，不需要去考慮。
這樣做的枚舉量為\(O(nm) \sim O(5 \times 10^4)\)，相比之前直接枚舉\(t_i\)的時間復雜度\(O(4 \times 10^6)\)來講，已經是飛躍了。
接著，假設前一趟擺渡車已經載了前\(k\)個人，那么我們要做的就只有兩件事：
- 再枚舉一個\(l\)，得到\(f[k][l]\)的最小值。
- 計算出第\(k+1\)個人到第\(i\)個人等候當前這趟擺渡車的等候時間和。
在狀態轉移方程中的體現就是：
\[f[i][j]=\min_{0 \leqslant k < i,0 \leqslant l < m} \{f[k][l]+col(k+1,i,t_i+j)\}\]
這當中，\(col(k+1,i,t_i+j)\)表示第\(k+1\)個乘客到第\(i\)個乘客等候發車時間為\(t_i+j\)的那趟擺渡車的時間和。
這里也有一個地方要注意：在枚舉\(k\)和\(l\)時，要滿足\(t_k+l<t_{k+1}\)。
理由和上面一樣，是因為這樣做違反了\(\mathrm{DP}\)中狀態的定義。其實上面的這個狀態轉移方程并不嚴謹，不過本人會慢慢把它修改得嚴謹起來（其實下文中的修改過程就是本人在考場上的思路）。
但這個方程很重要，以后的所有優化全都源自于這個方程，為了節省篇幅，本人不會重述這個方程，所以請大家記住這個轉移方程。
先拋開正確性，我們可以來計算一下上面這個狀態轉移方程的時間復雜度。
- 首先，\(i\)和\(j\)必須枚舉，所以是\(O(nm)\)的時間復雜度。
- 其次，\(k\)和\(l\)也是要枚舉的，所以又是一個\(O(nm)\)。
- 最后，每次枚舉\(i,j,k,l\)，都要計算一次\(col\)函數，而這個\(col\)函數的時間復雜度是\(O(n)\)的。
綜上所述，這個狀態轉移方程的時間復雜度為\(O(nm)*O(nm)*O(n)=O(n^3m^2)\)。
這時間復雜度……也太可觀了吧
所以我們需要優化！優化！優化！
三、程序實現 or 剪枝
我們可以發現，這\(n\)個人中有一些人開始等候的時間是相同的。
對于這些人，我們可以進行去重（開一個結構體，把相同時間的人壓進一個結構體里面，結構體里則用一個變量表示這些人開始等候的時間，用另一個變量表示這些重復的人的人數）。
雖然這樣做時間復雜度會多增加了\(O(n\log n)\)，但這樣可以在\(\mathrm{DP}\)時減少很多繁瑣的特判。
我們來關注一下這個式子：\[col(k+1,i,t_i+j)\]
對于每個\(i,j\)，當\(k\)每增加一時，\(col\)的值就只會減掉\((t_i+j-t_k)*size_k\)（\(size_k\)表示結構體中第\(k\)個元素的重復的人的數量）。所以我們可以在枚舉每個\(i\)和\(j\)時，就把\(col(k+1,i,t_i+j)\)算出來（用一個變量\(val\)存起來），然后，每當\(k\)增加\(1\)，\(val\)就減去\((t_i+j-t_k)*size_k\)。
狀態轉移方程就變為：\[f[i][j]=\min_{0 \leqslant k < i,0 \leqslant l < m} \{f[k][l]+val\}\]
這樣一抽出來，時間復雜度就變成了\(O(nm(n+nm))=O(n^2m+n^2m^2)\)
只保留最高次項后，時間復雜度就降為了\(O(n^2m^2)\)！！！又是一個飛躍！！！
注意！接下來的內容全都是難點，請大家做好心理準備！
其實大家有沒有想過，枚舉\(l\)這個操作顯得有些多余，可不可以省去呢？（畢竟只是求一個最小值而已，我求完一次就把這個最小值存起來不就行了嗎？）
沒錯，上面的想法是正確的！
設
\[Min[i]= \min_{0 \leqslant j < m,t_i+j<t_{i+1}} \{f[i][j]\}\]則之前的狀態轉移方程可以簡化為：
\[f[i][j]=\min_{0 \leqslant k < i} \{Min[k]+val\}\]
\(Min[k]\)可以在求每個\(f[k][l]\)的時候順帶維護
因為這里只枚舉了\(i,j,k\)，所以\(\mathrm{DP}\)的時間復雜度是\(O(n^2m)\)！！！
## 這個時間復雜度足以通過本題了！！！
但是，這樣做真的是對的嗎？
假設有這樣一個例子：
（數軸上的兩個點表示的是乘客開始等候的時間，圈3和圈4表示兩個乘客在（結構體）數組中的編號）
這時，我們直接用\(Min[3]\)來為\(f[4]\)做\(\mathrm{DP}\)就不行了。
假設我們要求\(f[4][0]\)的值（也就是說最后一趟車的發車時間和第4個乘客開始等候的時間相同的情況），當我們枚舉到\(k=3\)的情況時，我們只能取\(0 \leqslant l \leqslant 1\)的情況。（如果\(l>1\)的話，前一趟車的時間就有可能和當前這趟車的時間重疊了，違反了\(\mathrm{DP}\)中狀態的定義！）
也就是說，不能直接用\(Min\)數組來\(\mathrm{DP}\)！（因為\(Min[3]\)包含了\(f[3][0]\)到\(f[3][4]\)的最小值，直接用會出錯！）
那應該怎么辦？（我在考場上最絕望的時刻就是思考這個問題的過程）
后來一想：可不可以直接特判呢？
## 事實證明，可以！
首先，對于每個\(i,j\)，我們都為其開一個變量\(lt=t_i+j-m\)作為一個“防護墻”。
對于每個\(k\)，如果\(t_k+m>lt\)，那么\(Min[k]\)就不適用于\(f[i][j]\)這個狀態（因為對于這個\(k\)，有些\(t_k+l\)加上\(m\)以后會和\(t_i+j\)重疊）
對于這些\(k\)，我們就重新幫它枚舉一個\(l\)（滿足\(t_k+l \leqslant lt\)，不然超過了會重疊）去\(\mathrm{DP}\)。
由此也可以得出，如果\(t_k>lt\)，就可以直接退出當前循環了。（因為你沒有\(l\)再去枚舉了）
這樣一來，狀態轉移方程就開始有些惡心了：
\[f[i][j]=\begin{cases} \min\ \{Min[k]+val\} & t_k+m \leqslant lt \\ \min\limits_{t_k+l \leqslant lt} \{ f[k][l]+val \} & t_k+m>lt \end{cases}\]
這樣優化后的時間復雜度是多少呢？
首先，無論如何，\(i(n)\)和\(j(m)\)是一定要枚舉的，所以時間復雜度至少會有\(O(nm)\)。
然后，我們可以把兩個方程分開考慮：
第一個方程枚舉了\(k(n)\)，時間復雜度為\(O(n)\)
因為\(k\)和\(l\)總共只會計算\(m\)次（因為只有當\(lt-t_k<m\)時才會進入第二種情況。而\(l\)每次至少增長\(1\)，最慢也就是\(O(m)\)而已）
所以第二條方程的時間復雜度為\(O(m)\)。
加起來就是\(O(nm(n+m))\)，因為\(n>m\)，所以可以簡化成\(O(n^2m)\)！這個時間復雜度可以通過本題！
至此，我們終于得出了此題的可行解法！
四、考場代碼
我的代碼在結構體邊界上有一些預處理，這個重在意會即可相信大家應該看得懂
#include<stdio.h> #include<algorithm> using namespace std;const int maxn=502,maxm=102; const int INF=0x7fffffff;int f[maxn][maxm]; int Min[maxn];int a[maxn];struct Node {int pos,num; }Mem[maxn]; int sz;int col(int l,int r,int pos) {int res=0;for(int i=l;i<=r;i++)res+=(pos-Mem[i].pos)*Mem[i].num;return res; }int main(int argc, char const *argv[]) {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);Mem[0].pos=-m*2-2;a[0]=-1;for(int i=1;i<=n;i++){if( a[i]^a[i-1] )Mem[++sz].pos=a[i];Mem[sz].num++;}Mem[sz+1].pos=Mem[sz].pos+m+2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)f[i][j]=INF;Min[i]=INF;}Min[0]=0;for(int i=1;i<=sz;i++)for(int j=0;j<min(m,Mem[i+1].pos-Mem[i].pos);j++){int pos=Mem[i].pos+j,lpos=pos-m;int val=col(1,i,pos);f[i][j]=val;for(int k=0; k<i and Mem[k].pos<=lpos ;k++){val-=(pos-Mem[k].pos)*Mem[k].num;//如果Mem[k+1].pos-1<=lpos，那么Min[k]照樣能用（因為Mem[k+1].pos-1也是l的邊界之一，只要l小于兩個邊界中較小的那個值，就可以直接用Min[k]）if( min( Mem[k].pos+m-1,Mem[k+1].pos-1 )<=lpos ) f[i][j]=min( f[i][j],Min[k]+val );else{for(int kk=0; Mem[k].pos+kk<Mem[k+1].pos and Mem[k].pos+kk<=lpos and kk<m;kk++)f[i][j]=min( f[i][j],f[k][kk]+val );}}Min[i]=min( Min[i],f[i][j] );}printf("%d",Min[sz]);return 0; }\(In\ a\ word\)，祝大家\(\mathrm{NOIP\ rp}\)++！
轉載于:https://www.cnblogs.com/info---tion/p/11277515.html
總結
以上是生活随笔為你收集整理的NOIP 2018【摆渡车】题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【2018NOIP普及组】T3 摆渡车
- 下一篇： 【NOIP2018普及组】【DP】摆渡车