文章目錄

• 前言
• 題目
• • 題目描述
  • 輸入格式
  • 輸出格式
  • 輸入輸出樣例
  • • 輸入1
    • 輸出1
    • 輸入2
    • 輸出2
• 解析
• • dp轉移
  • • 初始化
    • 真正的轉移
    • Code

---

前言

誰會想到這次模擬賽竟然會原題重考？？？上午還有人確認了不考原題

啊，真香，哎

雖說是原題，但是還是全部都忘完了。。。有了一個新的思路，調了接近一個小時原以為能$A$，$but$竟然只得了$35$分，還不如x某十分鐘暴力$30$分來得快QwQ

題目

題目描述

有 $n$ 名同學要乘坐擺渡車從人大附中前往人民大學，第i位同學在第 $t_i$分鐘去等車。只有一輛擺渡車在工作，但擺渡車容量可以視為無限大。擺渡車從人大附中出發、 把車上的同學送到人民大學、再回到人大附中（去接其他同學），這樣往返一趟總共花費$m$分鐘（同學上下車時間忽略不計）。擺渡車要將所有同學都送到人民大學。

凱凱很好奇，如果他能任意安排擺渡車出發的時間，那么這些同學的等車時間之和最小為多少呢？

注意：擺渡車回到人大附中后可以即刻出發。

輸入格式

第一行包含兩個正整數 $n,m$，以一個空格分開，分別代表等車人數和擺渡車往返 一趟的時間。
第二行包含 $n$ 個正整數，相鄰兩數之間以一個空格分隔，第 $i$ 個非負整數 $t_i$代表第 $i$ 個同學到達車站的時刻。

輸出格式

輸出一行，一個整數，表示所有同學等車時間之和的最小值（單位：分鐘）。

輸入輸出樣例

輸入1

5 1 3 4 4 3 5

輸出1

0

輸入2

5 5 11 13 1 5 5

輸出2

4

解析

還是就講以前$A$過的那個思路吧，畢竟現在這個我到現在還沒有調出來QAQ、、、

首先，應該能很容易的看出來是個$DP$，但是，應該怎么$D$呢？？

在這里引入一個比較好懂的思路，雖然空間耗費很比較大。。。

emmm，引入正題……

首先，設$dp[i][j][k]$的三維數組，對，你沒看錯，就是三維不然我怎么說空間有點大。。 $dp[i][j][k]$表示第$i$個人還要等$j$分鐘才能坐到車（這里的坐到車的意思是還有$j$分鐘車才會開，也就是說可能車已經到了，但是還得等人），同時（包括$i$）一共有$k$個人正在等這輛車。

至于為什么會這么想$dp$，額可能是因為二維太難想了罷、、、

說完了$dp$的定義，現在我們來想想轉移。

dp轉移

話說$dp$最難的就是這里了吧。。。

初始化

首先聲明，這道題是用逆推來做，至于為什么要這么做呢？ _{我也不知道 （逃}

這是因為最后的那幾個狀態要比最開始的狀態好想一些呀，不管怎么說，最后所有人都會被送到對面去。因此我們只需要枚舉有多少人和他一起搭"末班車"，他們會需要等多久才能等到這班車（亦或是車等人）。

for (int i = 0; i <= m; i++)for (int j = 1; j <= n; j++)dp[n][i][j] = i * j;

真正的轉移

接下來才是重點，剛剛全是想湊字數來著

首先，$i$肯定是從大到小枚舉（剛剛已經講過了），$j、k$是正向枚舉（其實反向應該也沒有太大問題，只是一般來說都是正向而已，大家可以試試）

然后我們看$dp[i][j][k]$到底如何轉移。有兩種情況：當車到的時候第$i+1$個人早就到了；當車到的時候第$i+1$個人還沒到。

我們先看第一種情況：

當車到的時候第$i+1$個人早就到了。這個時候等這個車的人實際上又多了一個。因此$dp[i][j][k]=dp[i+1][j?cha[i]][k+1]+cha[i]?k$，這里的$cha$數組代表著第i個人和第i+1個人的時間差，因此在$i+1$的狀態中，加上$i+1$這個人共有$k+1$個人在等這輛車。

接下來再看第二種情況：

當車到的時候第$i+1$個人還沒到，那么在這里我們繼續分成兩種情況討論，$a.$等$i+1$這個人一起上車；$b.$不等這個人，現在的$k$個人先走。而在$b$這個情況中，又會有兩種情況：$1)$ 第$i+1$個人不需要等車，直接就能乘到下一輛車；$2)$ 第$i+1$個人需要等車

因此$dp[i][j][k]=min(dp[i+1][0][k+1]+cha[i]?k,dp[i+1][max(j+m?cha[i],0)][1]+j?k)$

總結來說，$dp[i][j][k]=min?\begin{array}{c}dp[i+1][j?cha[i]][k+1]+cha[i]?k\\ (j>cha[i])\\ min\left\{\begin{array}{c}dp[i+1][0][k+1]+cha[i]?k\\ dp[i+1][max(j+m?cha[i],0)][1]+j?k\end{array}\right\}\\ (j<=cha[i])\end{array}?$

最后輸出$dp[1][0][1]$就行了。

注意$dp$數組清極大值后，在后面轉移時要判斷！！！

Code

#include <cstdio> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <set> #include <map> #include <string> #include <queue> #include <stack> #include <cstring> #include <iostream> using namespace std; #define reg register #define LL long long #define INF 0x3f3f3f3ftemplate<typename T> void re (T &x){x = 0;int f = 1;char c = getchar ();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar ();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + c - 48;c = getchar ();}x *= f; }template<typename T> void pr (T x){if (x < 0){putchar ('-');x = ~x + 1;}if (x / 10) pr (x / 10);putchar (x % 10 + 48); }#define N 500 #define M 100int n, m, t[N + 5], cha[N + 5]; int dp[N + 5][M + 5][N + 5];int main (){freopen ("bus.in", "r", stdin);freopen ("bus.out", "w", stdout);re (n); re (m);for (int i = 1; i <= n; i++)re (t[i]);sort (t + 1, t + 1 + n);for (int i = 1; i <= n; i++)cha[i] = t[i + 1] - t[i];memset (dp, INF, sizeof (dp));for (int i = 0; i <= m; i++)for (int j = 1; j <= n; j++)dp[n][i][j] = i * j;for (int i = n - 1; i; i--)for (int j = 0; j <= m; j++)for (int k = 1; k <= i; k++)if (j > cha[i]){int x = dp[i + 1][j - cha[i]][k + 1];if (x == INF) x = 0;dp[i][j][k] = min (dp[i][j][k], x + cha[i] * k);}else{int x1 = dp[i + 1][0][k + 1], x2 = dp[i + 1][max (0, j + m - cha[i])][1];if (x1 == INF) x1 = 0;if (x2 == INF) x2 = 0;dp[i][j][k] = min (dp[i][j][k], min (x1 + cha[i] * k, x2 + j * k));}pr (dp[1][0][1]);putchar (10);return 0; }

總結

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

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