小韦老师@神犇营-USACO1.3.2-修理牛棚

题目：

描述

题意：
在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 这些牛在互相挨着的排成一排的牛棚中过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。
给出:可能买到的木板最大的数目 M (1 <= M <= 50)；牛棚的总数 S (1 <= S <= 200)； 牛棚里牛的总数 C (1 <= C <= S)； 和牛所在的牛棚的编号 stall_number (1 <= stall_number <= S), 计算拦住所有有牛的牛棚所需木板的最小总长度。
输出所需木板的最小总长度作为答案。
注意：
牛棚的长度为被拦住的牛棚总数量。

输入

第 1 行: M ， S 和 C (每两个数之间用一个空格分开) 。
第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

输出

单独的一行包含一个整数表示被拦住的牛棚总数量。

输入样例1

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

输出样例1

25

题解：

破题：

总共有 M 块木板，有 C 头牛，在把所有牛都拦住的前提下，求被拦住的牛棚总数量的最小值。

思路：

方法一：贪心算法
用变量 ans 表示拦住的牛棚数量的最小值，并且将 ans 初始化为 0。
（1）计算有牛的牛棚连通块的块数 num，若 num ≤ M，则转到（2），否则转到（3）。
（2）num ≤ M 说明木板数比牛的数量多，则 ans = C，因为至少要保证每头牛都要被拦住。
（3）如果 M < C，则首先要将牛所在的牛棚号进行升序排列，求出每一个间隔的大小，存在一个数组 mid 中，将间隔的数组进行升序排列，初始化 index 为 0，转到（4）。
（4）如果 num > M，则循环执行 ans += mid[index++]，num–，否则结束循环。
（5）输出 ans 即为所求。
方法二：动态规划
用数组 stall 来存储有牛的牛棚编号，需要升序排列。
用 f[i][j] 来作为描述信息，表示前 i 块木板挡住前 j 个有牛的牛棚的最小长度（这里注意是有牛棚的牛棚，j 不是牛棚编号，而是 stall 数组的编号）。
（1）当 j = 1 时，f[i][j] = 1
【注】
当 j = 1，说明只有一个牛棚里有牛，则只需要挡住这一个有牛的牛棚就可以，所以最小长度为 1。
（2）当 i = 1 时，f[i][j] = stall[j] - stall[1] + 1
【注】
当 i = 1 时，说明只有一块木板，则需要挡住的最小长度是从第 1 个有牛的牛棚到第 j 个有牛的牛棚。
（3）当 i != 1 && j != 1 时，f[i][j] = min(f[i-1][j-1] + 1, f[i][j - 1] + stall[j] - stall[j - 1])
【注】
f[i - 1][j - 1] 表示的是前 i - 1 个木板挡住了前 j - 1 个有牛的牛棚的最小长度，所以第 i 块木板就给第 j 个有牛的牛棚，所以加一即可。
f[i][j-1] 表示前 i 个木板挡住了前 j - 1 个有牛的牛棚的最小总长度，现在已经没有木板了，只能把挡住第 j - 1 的那个木板延伸到第 j 个有牛的牛棚，所以增加的长度为 stall[j] - stall[j - 1]

完整代码：

方法一：贪心算法

#include<bits/stdc++.h>

using namespace std;

const int N = 210;
int m;  // 最大木板数
int s;  // 牛棚总数
int c;  // 牛的总数
int stall[N];  // 有牛的牛棚编号
int mid[N];  // 有牛的牛棚之间的间隔

int block() {
	int num = 1;  // 记得要初始化为 1
	for (int i = 0; i < c - 1; i++) {
		if (stall[i + 1] != stall[i] + 1) {
			num++;
		}
	}
	return num;  // 记得返回
}

void cal_mid() {
	int index = 0;  // 数组下标
	for (int i = 1; i < c; i++) {
		// m 为间隔
		int m = stall[i] - stall[i - 1] - 1;
		// 若有间隔，则将间隔存到数组 mid 中
		if (m) mid[index++] = m;
	}
	sort(mid, mid + index);  // 记得升序排序
}

int main() {
    
	cin >> m >> s >> c;
	for (int i = 0;  i < c; i++) {
		cin >> stall[i];
	}
	sort(stall, stall + c);
	int num = block();
	int ans = 0;  // 被拦住的牛棚总数量的最小值
	if (num <= m) ans = c;
	else {
		cal_mid();
		int index = 0;  // 数组下标
		while (num > m) {
			ans += mid[index++];  // 依次加上间隔数
			num--;  // 连通的块数减一
		}
		ans += c;
	}
	cout << ans;
	
	return 0;
}

方法二：动态规划

#include <bits/stdc++.h>

using namespace std;

const int N = 210;
int m;  // 最大木板数
int s;  // 牛棚总数
int c;  // 牛的总数
int stall[N];  // 有牛的牛棚编号
int f[N][N];

int main() {
    
	cin >> m >> s >> c;
	for (int i = 1;  i <= c; i++) {
		cin >> stall[i];
	}
	// 将有牛的牛棚升序排列，记得要加 1
	sort(stall + 1, stall + c + 1);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= c; j++) {
			if (j == 1) {  // 只有一个牛棚有牛
				f[i][j] = 1;
			} else if (i == 1) {  // 只有一块木板
				f[i][j] = stall[j] - stall[1] + 1;
			} else {
				f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j - 1] + stall[j] - stall[j - 1]);
			}
		}
	}
	// 输出结果
	cout << f[m][c];
	
	return 0;
}