USACO Section 1.3 Barn Repair 解题报告

题目

题目描述

某农夫有一个养牛场，所有的牛圈都相邻的排成一排(共有S个牛圈)，每个牛圈里面最多只圈养一头牛。有一天狂风卷积着乌云，电闪雷鸣，把牛圈的门给刮走了。幸运的是，有些牛因为放假，所以没在自己的牛圈里(只有C个牛圈里面有牛)。现在农夫需要去用木板将牛圈的门补好，为了快速修复，农夫可以用一块长的木板直接将相邻连续的几个牛圈一起钉好封闭。现在有一个木板供应商，他能够供应M块木板，每块木板的长度任意。农夫想让最终消耗的木板总长度最小，请编写一个程序计算。

more

数据范围

1. 1 <= M <= 50
2. 1 <= S <= 200
3. 1 <= 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;

}