【NOIP 2018 T3】摆渡车

你的名字 2021-11-19 14:36 307阅读 0赞

### 文章目录 ###

*  前言
 *  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  输入输出样例
     *   *  输入1
         *  输出1
         *  输入2
         *  输出2
 *  解析
 *   *  dp转移
     *   *  初始化
         *  真正的转移
         *  Code

--------------------

# 前言 #

谁会想到这次模拟赛竟然会原题重考？？？上午还有人确认了不考原题

啊，真香，哎

虽说是原题，但是还是全部都忘完了。。。有了一个新的思路，调了接近一个小时原以为能 A A A， b u t but but竟然只得了 35 35 35分，还不如x某十分钟暴力 30 30 30分来得快QwQ

# 题目 #

## 题目描述 ##

有  n n n 名同学要乘坐摆渡车从人大附中前往人民大学，第i位同学在第  t i t\_i ti分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费 m m m分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

## 输入格式 ##

第一行包含两个正整数  n , m n,m n,m，以一个空格分开，分别代表等车人数和摆渡车往返 一趟的时间。  
第二行包含  n n n 个正整数，相邻两数之间以一个空格分隔，第  i i i 个非负整数  t i t\_i ti代表第  i i i 个同学到达车站的时刻。

## 输出格式 ##

输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

## 输入输出样例 ##

### 输入1 ###

5 1 
    3 4 4 3 5

### 输出1 ###

### 输入2 ###

5 5 
    11 13 1 5 5

### 输出2 ###

# 解析 #

还是就讲以前 A A A过的那个思路吧，毕竟现在这个我到现在还没有调出来QAQ、、、

首先，应该能很容易的看出来是个 D P DP DP，但是，应该怎么 D D D呢？？

在这里引入一个比较好懂的思路，虽然空间耗费很比较大。。。

emmm，引入正题……

> 首先，设 d p \[ i \] \[ j \] \[ k \] dp\[i\]\[j\]\[k\] dp\[i\]\[j\]\[k\]的三维数组，对，你没看错，就是三维不然我怎么说空间有点大。。  d p \[ i \] \[ j \] \[ k \] dp\[i\]\[j\]\[k\] dp\[i\]\[j\]\[k\]表示第 i i i个人还要等 j j j分钟才能坐到车（这里的坐到车的意思是还有 j j j分钟车才会开，也就是说可能车已经到了，但是还得等人），同时（包括 i i i）一共有 k k k个人正在等这辆车。

至于为什么会这么想 d p dp dp，额可能是因为二维太难想了罢、、、

说完了 d p dp dp的定义，现在我们来想想转移。

## dp转移 ##

话说 d p dp dp最难的就是这里了吧。。。

### 初始化 ###

首先声明，这道题是用逆推来做，至于为什么要这么做呢？ 我也不知道 （逃

这是因为最后的那几个状态要比最开始的状态好想一些呀，不管怎么说，最后所有人都会被送到对面去。因此我们只需要枚举有多少人和他一起搭"末班车"，他们会需要等多久才能等到这班车（亦或是车等人）。

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

### 真正的转移 ###

接下来才是重点，刚刚全是想凑字数来着

首先， i i i肯定是从大到小枚举（刚刚已经讲过了）， j 、 k j、k j、k是正向枚举（其实反向应该也没有太大问题，只是一般来说都是正向而已，大家可以试试）

然后我们看 d p \[ i \] \[ j \] \[ k \] dp\[i\]\[j\]\[k\] dp\[i\]\[j\]\[k\]到底如何转移。有两种情况：当车到的时候第 i + 1 i+1 i\+1个人早就到了；当车到的时候第 i + 1 i+1 i\+1个人还没到。

我们先看第一种情况：

**当车到的时候第 i + 1 i+1 i\+1个人早就到了。这个时候等这个车的人实际上又多了一个。因此 d p \[ i \] \[ j \] \[ k \] = d p \[ i + 1 \] \[ j − c h a \[ i \] \] \[ k + 1 \] + c h a \[ i \] ∗ k dp\[i\]\[j\]\[k\] = dp\[i + 1\]\[j - cha\[i\]\]\[k + 1\] + cha\[i\] \* k dp\[i\]\[j\]\[k\]=dp\[i\+1\]\[j−cha\[i\]\]\[k\+1\]\+cha\[i\]∗k，这里的 c h a cha cha数组代表着第i个人和第i+1个人的时间差，因此在 i + 1 i+1 i\+1的状态中，加上 i + 1 i+1 i\+1这个人共有 k + 1 k+1 k\+1个人在等这辆车。**

接下来再看第二种情况：

**当车到的时候第 i + 1 i+1 i\+1个人还没到，那么在这里我们继续分成两种情况讨论， a . a. a.等 i + 1 i+1 i\+1这个人一起上车； b . b. b.不等这个人，现在的 k k k个人先走。而在 b b b这个情况中，又会有两种情况： 1 ) 1) 1) 第 i + 1 i+1 i\+1个人不需要等车，直接就能乘到下一辆车； 2 ) 2) 2) 第 i + 1 i+1 i\+1个人需要等车**

因此 d p \[ i \] \[ j \] \[ k \] = m i n ( d p \[ i + 1 \] \[ 0 \] \[ k + 1 \] + c h a \[ i \] ∗ k , d p \[ i + 1 \] \[ m a x ( j + m − c h a \[ i \] , 0 ) \] \[ 1 \] + j ∗ k ) 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(dp\[i\+1\]\[0\]\[k\+1\]\+cha\[i\]∗k,dp\[i\+1\]\[max(j\+m−cha\[i\],0)\]\[1\]\+j∗k)

总结来说， d p \[ i \] \[ j \] \[ k \] = m i n \{ d p \[ i + 1 \] \[ j − c h a \[ i \] \] \[ k + 1 \] + c h a \[ i \] ∗ k ( j > c h a \[ i \] ) m i n \{ d p \[ i + 1 \] \[ 0 \] \[ k + 1 \] + c h a \[ i \] ∗ k d p \[ i + 1 \] \[ m a x ( j + m − c h a \[ i \] , 0 ) \] \[ 1 \] + j ∗ k \} ( j < = c h a \[ i \] ) \} dp\[i\]\[j\]\[k\] = min \\begin\{Bmatrix\} dp\[i + 1\]\[j - cha\[i\]\]\[k + 1\] + cha\[i\] \* k\\\\ (j > cha\[i\])\\\\ min \\begin\{Bmatrix\} dp\[i +1\]\[0\]\[k + 1\] + cha\[i\] \* k\\\\ dp\[i + 1\]\[max (j + m - cha\[i\], 0)\]\[1\] + j \* k \\end\{Bmatrix\}\\\\ (j <= cha\[i\]) \\end\{Bmatrix\} dp\[i\]\[j\]\[k\]=min⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧dp\[i\+1\]\[j−cha\[i\]\]\[k\+1\]\+cha\[i\]∗k(j>cha\[i\])min\{ dp\[i\+1\]\[0\]\[k\+1\]\+cha\[i\]∗kdp\[i\+1\]\[max(j\+m−cha\[i\],0)\]\[1\]\+j∗k\}(j<=cha\[i\])⎭⎪⎪⎪⎪⎬⎪⎪⎪⎪⎫

最后输出 d p \[ 1 \] \[ 0 \] \[ 1 \] dp\[1\]\[0\]\[1\] dp\[1\]\[0\]\[1\]就行了。

注意 d p dp 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 0x3f3f3f3f
    
    template<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 100
    
    int 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;
    }