题目
题目描述
某农夫有一个养牛场，所有的牛圈都相邻的排成一排(共有S个牛圈)，每个牛圈里面最多只圈养一头牛。有一天狂风卷积着乌云，电闪雷鸣，把牛圈的门给刮走了。幸运的是，有些牛因为放假，所以没在自己的牛圈里(只有C个牛圈里面有牛)。现在农夫需要去用木板将牛圈的门补好，为了快速修复，农夫可以用一块长的木板直接将相邻连续的几个牛圈一起钉好封闭。现在有一个木板供应商，他能够供应M块木板，每块木板的长度任意。农夫想让最终消耗的木板总长度最小，请编写一个程序计算。
数据范围
1 <= M <= 501 <= S <= 2001 <= C <= S
样例输入
第一行输入M S C三个整数，接下来输入有牛的牛圈编号
4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43
样例输出
25
解题思路
我们可以证明将M块木板全部用上的时候可以让最终的木板总长度最少(这是比较明显的结论)，利用贪心的思想，首先将编号进行排序，然后用一块木板从最小编号的牛圈开始，一直覆盖到最大编号的牛圈。之后我们需要找牛圈之间的间隔，每次都找最大的间隔，然后从中隔断，直到将一块木板拆成M块木板。
当M > C时，我们可以进行特判，或者利用下面这种写法可以减少特判。
解题代码
/*
ID: yinzong2
PROG: barn1
LANG: C++11
*/
#define MARK
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 210;
int m, s, c;
int stalls[MAXN];
bool vis[MAXN];
int main() {
#ifdef MARK
freopen("barn1.in", "r", stdin);
freopen("barn1.out", "w", stdout);
#endif // MARK
while(~scanf("%d%d%d", &m, &s, &c)) {
for(int i = 0; i < c; i++) {
scanf("%d", &stalls[i]);
vis[i] = false;
}
sort(stalls, stalls+c);
int _min = stalls[c-1] - stalls[0] + 1;
for(int i = 1; i < m; i++) {
int temp = 0;
int id = 0;
//找到当前最大的间隔
for(int j = 0; j < c-1; j++) {
if(!vis[j] && temp < (stalls[j+1]-stalls[j]-1)) {
temp = (stalls[j+1]-stalls[j]-1);
id = j;
}
}
vis[id] = true;
_min -= temp;
}
printf("%d\n", _min);
}
return 0;
}
解题思路(Type 2)
我们同样可以利用贪心的思想，将上面的思路进行反向操作，我们首先对于每个牛圈上都单独覆盖一块木板，那么此时就有C块木板。如果M > C我们就特判，否则，我们每次寻找牛圈之间的最小间隔，然后将两个牛圈之间用一块木板覆盖，这样我们可以减少一块木板，最终一直合并，减少到M块木板。
解题代码(Type 2)
/*
ID: yinzong2
PROG: barn1
LANG: C++11
*/
#define MARK
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAXN = 210;
int m, s, c;
int stalls[MAXN];
bool vis[MAXN];
int main() {
#ifdef MARK
freopen("barn1.in", "r", stdin);
freopen("barn1.out", "w", stdout);
#endif // MARK
while(~scanf("%d%d%d", &m, &s, &c)) {
for(int i = 0; i < c; i++) {
scanf("%d", &stalls[i]);
vis[i] = false;
}
sort(stalls, stalls+c);
int ans = c;
int board = c;
while(board > m) {
int _min = MAXN;
int id = 0;
//寻找最小间隔
for(int i = 0; i < c-1; i++) {
if(!vis[i] && _min > (stalls[i+1]-stalls[i]-1)) {
_min = (stalls[i+1]-stalls[i]-1);
id = i;
}
}
vis[id] = true;
ans += _min;
board--;
}
printf("%d\n", ans);
}
return 0;
}
解题思路(Type 3)
我们还可以利用动态规划的思想来解决这个问题，我们首先定义一个函数dis(i, j)，这个函数可以计算一块木板从第 i 个牛圈覆盖到第 j 个牛圈需要的木板长度。之后我们接着定义dp[i][j]，它代表利用 i 块木板，一直覆盖到编号为 j 的牛圈所需要的最少的木板长度。所以我们最终要求的就是dp[M][C]。
状态转移方程如下：dp[i][j] = min(dp[i][j], min(dp[i-1][k]+dis(k+1, j), dp[i][k]+dis(k, j)-1)); (1 <= k < j)
解题代码(Type 3)
/*
ID: yinzong2
PROG: barn1
LANG: C++11
*/
#define MARK
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 210;
int m, s, c;
int stalls[MAXN];
int dp[55][MAXN];
int dis(int i, int j) {
return stalls[j]-stalls[i]+1;
}
int main() {
#ifdef MARK
freopen("barn1.in", "r", stdin);
freopen("barn1.out", "w", stdout);
#endif // MARK
while(~scanf("%d%d%d", &m, &s, &c)) {
for(int i = 1; i <= c; i++) {
scanf("%d", &stalls[i]);
}
if(m > c) {
printf("%d\n", c);
continue;
}
sort(stalls+1, stalls+1+c);
for(int i = 1; i <= c; i++) {
dp[1][i] = dis(1, i);
}
for(int i = 2; i <= m; i++) {
for(int j = 1; j <= c; j++) {
dp[i][j] = MAXN;
for(int k = 1; k < j; k++) {
dp[i][j] = min(dp[i][j], min(dp[i-1][k]+dis(k+1, j), dp[i][k]+dis(k, j)-1));
}
}
}
printf("%d\n", dp[m][c]);
}
return 0;
}