題面

1.前言

我記得這是上上上…(此處省略多個“上”字) 次考試的題了，結果我思路想到了，但是沒打出來(因為我腦子what了，只用一個變量去完成人家兩個數組完成的事，代碼十分麻煩，細節也多)，這次又雙叒花了很長時間去debug。
我愛死這個擺渡車了，以后我出去都坐擺渡車

2.分析

狀態: dp[i]表示在i這個時刻，車在人大附中，最小的等車時間和
易得 狀態轉移方程為：
$$dp[i]=min(dp[j]+[j,i]時刻之間的等車時間和)(0<=j<i)$$

時間復雜度: $O(n?n?n)$

偽代碼

for (i: 1 ~ n) {for (j: 1 ~ i - 1) {int cnt = 0;for (k: j ~ i) {cnt += k時刻到來的人所需等待的時間 }dp[i] = min (dp[i], dp[j] + cnt);} }

ATTENTION: 最終的答案不在 $dp[max(t[i])]$ 里，因為將時間第二大的人送走后返回到人大附中的時間是 $第二大的時間+m$ ，所以答案應該為

$$min(dp[i])(max(t[j])<=i<max(t[j])+m)$$

3.優化

1.我們先分析車，車的停留時間是不會超過m的（因為Ta可以在相同的狀態下多跑一趟，這肯定比少跑一趟的結果優）

2.我們能不能用更快的時間去計算出[j, i]時刻之間的等車時間和呢？答案是可以的，我們可以用一個前綴和數組來實現，具體操作見下

for (int i = 1; i <= n; i++) {scanf ("%lld", &a[i]);r = Max (r, a[i]);prenum[a[i]]++; pret[a[i]] += a[i]; } for (int i = 1; i < r + m; i++) prenum[i] += prenum[i - 1], pret[i] += pret[i - 1];(prenum[i] - prenum[j]) * i - (pret[i] - pret[j])即為[j, i]時刻之間的等車時間和

4.代碼

#include <cstdio> #define LL long longconst int MAXN = 505; const int MAXT = 5 * 1e6 + 5;int n, m;LL r; LL a[MAXN], prenum[MAXT], pret[MAXT], dp[MAXT];LL Max (LL x, LL y) { return x > y ? x : y; } LL Min (LL x, LL y) { return x < y ? x : y; }int main () {scanf ("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf ("%lld", &a[i]);r = Max (r, a[i]);prenum[a[i]]++; pret[a[i]] += a[i];}if (m == 1) {printf ("0");return 0;}for (int i = 1; i < r + m; i++) prenum[i] += prenum[i - 1], pret[i] += pret[i - 1];for (int i = 1; i < r + m; i++) {dp[i] = i * prenum[i] - pret[i];for (int j = Max (i - m * 2 + 1, 0); j <= i - m; j++) {dp[i] = Min (dp[i], dp[j] + (prenum[i] - prenum[j]) * i - (pret[i] - pret[j]));}}LL ans = 0x7f7f7f7f7f7f7f;for (int i = r; i < r + m; i++) ans = Min (ans, dp[i]);printf ("%lld", ans);return 0; }

注：我這個代碼用C++(NOI)提交， 就算 不擇手段的 優化，Ta也過不了，若諸位大佬有更好的算法，請不吝賜教。 orz

總結

以上是生活随笔為你收集整理的【NOIP2018普及组】摆渡车 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。