【讲解】缺席的神官——动态规划模型

缺席的神官——动态规划模型

链接：https://ac.nowcoder.com/acm/contest/3036/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

面前的巨汉，让我想起了多年前的那次，但这个巨汉身上散布着让人畏惧害怕的黑雾。即使看不到脸，但是威严却在这个从者身边不断围绕。
「吾乃七骑之中的骑士(rider)，你们就是御主所说的阻扰者吧」
「是」我从雪茄盒里面掏出一根雪茄，想稍微冷静一下。
「那便无需多言了」和我签订了暂时契约的理查一世倒是直接拔剑了，如此看来查理一世的职介就是剑士(saber)。
「我看你的御主倒是没有这个想法吧」
他似乎看出了我的想法，虽然只是亡魂的影子，但也曾是人，能洞察人心。
「您是这样的想法吗」理查一世把剑收了起来。
「是啊，虽然参与圣杯战争的御主和从者目的是实现愿望，但既然是残缺的圣杯，我也会猜想是否从者对圣杯的渴望并没有那么高，是否有值得交涉的余地」
「哈」巨汉笑了，「真是大胆的妄想啊，但你应该明白圣杯显现的方法吧，所以这一切都是不可避免的。但我也不想使用武力，解答我的困惑吧，魔术师，如果你们能回答出来，我就会放弃」
「我明白了，洗耳恭听」
「古时有一个懒惰的祭司，而祭司在连续m天内必须一直去神庙内工作，但祭司的怠惰在诱惑着祭司，于是祭司决定这段时间内只选出k个连续的时间段去神庙工作，但是高级祭司(祭司的上级)又会定期对神庙内的工作人员进行点名。祭司不想因此失去这份工作，所以提前知道了高级祭司会点名n次以及每次点名的日子。所以祭司把点名的日子纳入工作的日子当中的同时又尽可能的偷懒。那么，这个祭司到底工作了多少天呢」
「这个答案很简单，荷鲁斯」

输入描述:

第一行输入三个整数n,m,k (1 <= n <= 2000) (n <= m <= 10^9) (1<= k <= n)，分别为高级祭司的点名次数,原本需要工作的天数和懒惰的祭司的工作次数。第二行输入n个数字ai (1 <= ai <= m),为高级祭司检查的日期。
输入保证对于任意的i,j (1<= i<j <= n)，都有ai < aj。

输出描述:

输出懒惰的祭司进行工作的最少天数

示例1

输入

4 100 2
20 30 75 80

输出

17

说明

样例的2段为[20,30],[75,80]，进行工作的最少天数为：11+6=17

---

问题分析：

先吐槽一下这道题目，哇，这个祭司好惨啊，最长要工作10^(9)天，也就是90亿天，27万年，难怪要偷懒（笑）。这道题先考察的一定是读题能力，信息太多，输入的数据也很多，一不小心就会弄混（事实证明，我的第一次WA就是因为弄混了变量）

一开始我有点不太懂的是工作次数，其实我们都懂，要想偷最大的懒，最简单的方法就是在点名的日子去就好了，其他日子都不去。

但这个祭司可能家里离神庙比较远（戏真多），所以每次

决定这段时间内只选出k个连续的时间段去神庙工作

也就是说如果次数比较少，那每次都要从一个检查日住到下一个检查日，然后等待第二个检查日后的第二天卷款回家。

以题目的例子为例

4 100 2
20 30 75 80

只去两次，那么正常人的四维就是把每种情况都算一遍，然后把最大时间间隔的两个日期敲掉，也就是30-75足足有44天时间都不去。

如果是三次呢？那就再敲掉20-30的9天，也就是祭司只在第20、30、75-80天在神庙，也就是8天

如果是四次呢？那当然就是4天咯，就是20、30、75、80这四天去。

嗯，不知道你有没有冥冥的感受到，如果去1次 那就是两端的值，去2次，那就找出最大间隔的天数然后去掉，去3次，就再减去第二大间隔的天数…

那，这后面一次的数据是不是要利用前一次数据的结果呀？那这不就是大名鼎鼎的

动态规划

如果你不太懂动态规划，可以看下我之前写过的一篇文章

动态规划27k字超详细保姆级入门讲解

下面我用下我上篇文章自创的DP设计方法

DP设计

1.明确到底是几维的DP，是否有必要升级维数或降低

2.如何将大问题化为小问题

3.定义数组元素的含义，存放的数值的意义所在

4.找出DP状态转移方程

5.找出初始值、注意临界值，递推/递归总设计思路

问题一：

一维，最低维数了

问题二：

要计算去n次的天数，要先计算n-1；要计算n-1，要先计算n-2…最后要先计算去1次的结果

问题三：

dp[i]表示的是去i次最少要去多少天

问题四：

dp[i] = dp[i-1] - max

问题五：

初始值就是dp[1] = 最后一个检查日-第一个检查日+1

一不小心就写了1500字了，求点赞收藏关注~

---

AC代码：

#include <bits/stdc++.h>
using namespace std;

long long int checkday[2020];
long long int dis[2020];
long long int dp[2020]; 

int main()
{
	int checktimes, worktimes;
	long long int times;
	cin >> checktimes >> times >> worktimes;
	

	for ( int i=1; i<=checktimes; i++ )
		cin >> checkday[i];
	
	//计算每个检查日之间的间隔，并找出最大值
	int max = 0;
	int index;
	for ( int i=2; i<=checktimes; i++ )
	{
		dis[i] = checkday[i]-checkday[i-1]-1;
		if ( max < dis[i] )
		{
			max = dis[i];
			index = i;
		}
	}
	
    //初始化DP
	dp[1] = checkday[checktimes] - checkday[1] + 1;
	
	//计算后边的DP，每次都重新找最大值
	for ( int i=2; i<=checktimes; i++ )
	{
		dp[i] = dp[i-1] - max;
		dis[index] = 0;
		max = 0;
		for ( int i=2; i<=checktimes; i++ )
		{
			if ( max < dis[i] )
			{
				max = dis[i];
				index = i;
			}
		}			
	}	
	
	dp[checktimes] = checktimes;
	cout << dp[worktimes] << endl;

} 

---

写在后面：

为了确保大家能够看懂这篇文章，我尽量每字每句都详细讲解，给出证明和解释，真心希望你能够在阅读此篇文章后从中多多少少有所收获。因此每篇文章我都投入了大量的时间和精力，去举例，去说明，去分析，如果你觉得这篇文章写的还不错，点赞、关注和收藏一键三连就是对我最大的鼓励啦，我以后也会写更多更高质量的文章！也欢迎一起讨论指出文章可能存在的逻辑问题~

开通了微信公众号 欢迎关注~精选CSDN的文章发布 更优质的排版 更丰富的学习资源分享