NOIP2018PJ T3 擺渡車（2023.10第二版題解）
題意：
時間軸上分布著$n$位乘客（$1\le n\le 500$），$i$號乘客的位置為$t_i$（$0\le t_i\le 4\times 10^6$），用互相距離不小于$m$的車次將時間軸分為若干部分，并管轄以自己為右端點的這個區(qū)間（除了第一趟車包括$0$，其他車次左開右閉），求最小費用和。每個車次的費用來自：管轄區(qū)間內(nèi)所有乘客與該車次的距離之和。
程序1（30pts）：
考慮DP。
設(shè)在$i$時刻等車的人共有$c_i$位，再設(shè)在$i$時刻發(fā)車的費用以及之前所有車次費用之和的最小值為$f_i$。
①若這是第一趟車，則累加$i$時刻之前所有人等車的時間：
$$f_i=\sum\limits_{j=0}^{i} c_j\times(i-j)$$
②若非第一趟車，則枚舉上一趟車發(fā)車的時間$j$，再累加$j+1$到$i$時刻的人等車的時間：
$$f_i=\mathop{min}\limits_{0\le j\le i-m}\{f_j+\sum\limits_{k=j+1}^i c_k\times(i-k)\}$$
考慮最終答案怎么算。假設(shè)最后一名乘客的位置為$T$，則最后一趟車次時間必在$[\,T,T+m\,)$中，取這些時間的$f_i$最小值即可。
DP做完了。然而時間復雜度為$O(T^3)$，只有$30$分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //設(shè)在i時刻等車的人共有c_i位 int f[T + M + 3]; //設(shè)在i時刻發(fā)車的費用以及之前所有車次費用之和的最小值為f_i //時間軸會用到T+m，對應的數(shù)組的范圍也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //統(tǒng)計c[]時刻等車的人的個數(shù) maxt = max(maxt, t[i]); } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟車最晚在maxt+m-1時發(fā)出 int tmp = 0; for(int j = 0; j <= i; j++) tmp += c[j] * (i - j); f[i] = tmp; //初值：如果此時發(fā)第一趟車的費用 for(int j = 0; j <= i - m; j++){ //如果上一趟車是j時刻發(fā)的 tmp = 0; for(int k = j + 1; k <= i; k++) //累加j+1~i時刻等車的人 tmp += c[k] * (i - k); f[i] = min(f[i], f[j] + tmp); //取最小值 } } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟車的時間可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序2（50pts）：
發(fā)現(xiàn)式子里有很多連續(xù)區(qū)間的運算，嘗試變形一下式子以便使用前綴和優(yōu)化。
$$\sum\limits_{j=0}^{i} c_j\times(i-j)=i\sum\limits_{j=0}^i c_j - \sum\limits_{j=0}^i j\times c_j$$
設(shè)$c_i$的前綴和為$C_i$，$i\times c_i$的前綴和為$S_i$，則原式
$$=i\times C_i - S_i$$
再看
$$\begin{matrix}\sum\limits_{k=j+1}^i c_k(i-k)&=i\sum\limits_{k=j+1}^i c_k-\sum\limits_{k=j+1}^i k\times c_k\\&=i(C_i-C_j)-(S_i-S_j)\end{matrix}$$
于是我們就可以$O(1)$轉(zhuǎn)移了，整體時間復雜度下降到$O(T^2)$，可以得到$50$分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //設(shè)在i時刻等車的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前綴和；i*c_i前綴和 int f[T + M + 3]; //設(shè)在i時刻發(fā)車的費用以及之前所有車次費用之和的最小值為f_i //時間軸會用到T+m，對應的數(shù)組的范圍也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //統(tǒng)計c[]時刻等車的人的個數(shù) maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟車最晚在maxt+m-1時發(fā)出 f[i] = i * C[i]-S[i]; //初值：如果此時發(fā)第一趟車的費用 for(int j = 0; j <= i - m; j++) //如果上一趟車是j時刻發(fā)的 f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟車的時間可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序3（70pts）：
DP轉(zhuǎn)移是枚舉上一步，而這個DP里每個狀態(tài)都從$0$狀態(tài)開始枚舉上一步，顯然有很多冗余，需要剪去無用轉(zhuǎn)移。
思考一下，發(fā)現(xiàn)我們不會切出一個長度$\ge 2m$的區(qū)間出來，因為這樣的區(qū)間至少可以多切一次，得到兩個長度$\ge m$的區(qū)間，總費用可能減少或者不變。
于是乎，若不是第一趟車，則
$$f_i=\mathop{min}\limits_{i-2m<j\le i-m}\{f_j+i(C_i-C_j)-(S_i-S_j)\}$$
現(xiàn)在我們的DP時間復雜度為$O(T\times m)$，理論得分$70$分。
（洛谷用了比較好的評測機，我這發(fā)差不多$1e9$的運算也A了）
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //設(shè)在i時刻等車的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前綴和；i*c_i前綴和 int f[T + M + 3]; //設(shè)在i時刻發(fā)車的費用以及之前所有車次費用之和的最小值為f_i //時間軸會用到T+m，對應的數(shù)組的范圍也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //統(tǒng)計c[]時刻等車的人的個數(shù) maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟車最晚在maxt+m-1時發(fā)出 f[i] = i * C[i]-S[i]; //初值：如果此時發(fā)第一趟車的費用 for(int j = max(0, i - m * 2 + 1); j <= i - m; j++) //如果上一趟車是j時刻發(fā)的 //注意j不能為負數(shù) f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟車的時間可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
程序4（100pts）：
看起來轉(zhuǎn)移已經(jīng)很簡潔了，但是算法的復雜度仍沒有達到要求。
思考一下，發(fā)現(xiàn)我們嘗試對每個時間位置($0\sim T+m$，約$4\times 10^6$)都算了一遍轉(zhuǎn)移，也就是嘗試在這個位置發(fā)了一輛車（由$f$的定義），但實際上有效發(fā)車的時間位置一定不會超過$n\times m$個（約$5\times 10^4$），我們可以剪去無用狀態(tài)。
換句話說，對于在$t_i$位置等車的人，接走他的車的時間位置一定在$[t_i,t_i+m)$范圍內(nèi)。
再換句話說，如果時間軸上有一段長度不少于$m$的區(qū)間沒有任何乘客，那么我們在這個區(qū)間右端發(fā)不發(fā)車費用都一定不會增加，可以直接繼承狀態(tài)，即
$$f_i\leftarrow f_{i-m},\qquad C_i=C_{i-m}$$
算算時間復雜度，只在有效發(fā)車時間位置做轉(zhuǎn)移，所以總時間復雜度是$O(T+n\times m^2)$，可以得到滿分。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 500; const int M = 100; const int T = 4e6; int n, m, t[N + 3]; int c[T + M + 3]; //設(shè)在i時刻等車的人共有c_i位 int C[T + M + 3], S[T + M + 3]; //c_i前綴和；i*c_i前綴和 int f[T + M + 3]; //設(shè)在i時刻發(fā)車的費用以及之前所有車次費用之和的最小值為f_i //時間軸會用到T+m，對應的數(shù)組的范圍也是T+M int main(){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); int maxt = 0; for(int i = 1; i <= n; i++){ scanf("%d", &t[i]); c[t[i]]++; //統(tǒng)計c[]時刻等車的人的個數(shù) maxt = max(maxt, t[i]); } C[0] = c[0]; S[0] = 0; for(int i = 1; i <= maxt + m; i++){ C[i] = C[i - 1] + c[i]; S[i] = S[i - 1] + i * c[i]; } // memset(f, 0x3f, sizeof f); for(int i = 0; i < maxt + m; i++){ //最后一趟車最晚在maxt+m-1時發(fā)出 if(i >= m && C[i] == C[i - m]){ //如果在i發(fā)車接不到任何人 f[i] = f[i - m]; //直接繼承狀態(tài)，費用不會變化 continue; } f[i] = i * C[i]-S[i]; //初值：如果此時發(fā)第一趟車的費用 for(int j = max(0, i - m * 2 + 1); j <= i - m; j++) //如果上一趟車是j時刻發(fā)的 //注意j不能為負數(shù) f[i] = min(f[i], f[j] + i * (C[i] - C[j]) - (S[i] - S[j])); } int ans = 1<<30; for(int i = maxt; i < maxt + m; i++) //最后一趟車的時間可以是maxt~maxt+m-1 ans = min(ans, f[i]); printf("%d", ans); return 0; }
小結(jié)：
掌握DP的基礎(chǔ)優(yōu)化方法：前綴和優(yōu)化、剪去無用轉(zhuǎn)移、剪去無用狀態(tài)，做到不寫腦殘的DP。
浙公網(wǎng)安備 33010602011771號