题目

{% fold 点击显/隐题目 %}

题解

这道题有多种不同的思路

贪心

首先假定我们用一个木板拦住所有的牛,当我们有多于一个木板的时候,我们的任务就是选一个最大的区间,从这里把木板拆成两个

当有多个木板时同理,不停寻找最大的区间即可

细节比较多,可以把中间变量输出出来进行测试

需要特别注意的是: 牛所在的牛栏并不是有序输出的,同时存在没有牛和木板比牛的情况

动态规划

动态规划最重要的是转移方程

可以看出自变量的应该是木板数和牛栏数,也即有:
dp(i,j) 表示前i个牛栏使用j个木板所需要的最小木板总长度

那么就可以看出在已经有dp(i-1,j)的情况下,又加入一个新的牛栏(有牛),存在两种处理方案：

• 用一块新的木板 dp(i-1,j-1)+1
• 延长上一块木板 dp(i-1,j)+a[i]-a[i-1]

也即 dp(i,j) = min( dp(i-1,j-1)+1, dp(i-1,j)+a[i]-a[i-1] )

然后需要处理的就是边界条件
按照实际含义来想,dp(0,k) 表示0个牛栏需要的木板数,显然应该是0
而 dp(k,0) (k!=0) 表示没有木板的情况下,拦住k个有牛的牛栏,应该是无穷大

综上:
{% raw %}$
dp(i,j) = \left{\begin{matrix}
0 & i=0\
INF & i \neq 0,j=0\
min(dp(i-1,j-1)+1,dp(i-1,j)+a[i]-a[i-1]) & 其他
\end{matrix}\right.
${% endraw %}

代码

贪心

{% fold 点击显/隐代码 %}```cpp 修理牛棚(贪心) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
using namespace std;

const int maxn = 205;
int a[maxn], b[maxn];
int m, s, c;

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

while (cin >> m >> s >> c) {
    for (int i = 0; i < c; i++)
        cin >> a[i];
    sort(a,a+c);
    if (c == 0 || m >= c ) {
        cout << c << endl;
    } else {
        for (int i = 0; i < c - 1; i++)
            b[i] = a[i + 1] - a[i] - 1;
        sort(b, b + c - 1);

        int ans = a[c - 1] - a[0] + 1;
        // cout<<ans<<endl;
        for (int i = 0; i < m - 1; i++) {
            // cout<<b[c-1-i]<<endl;
            ans -= b[c - 2 - i];
        }
        cout << ans << endl;
    }
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}

## 动态规划
{% fold 点击显/隐代码 %}```cpp 修理牛棚(dp) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 205;
const int INF = 0x3f3f3f;
int a[maxn];
int m, s, c;
int dp[maxn][maxn];

int main() {
#ifdef debug
    freopen("in.txt", "r", stdin);
    int START = clock();
#endif
    cin.tie(0);
    cin.sync_with_stdio(false);

    a[0] = 0;
    while (cin >> m >> s >> c) {
        for (int i = 1; i <= c; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + c);

        for (int i = 0; i <= c; i++)
            dp[i][0] = INF;
        memset(dp[0], 0, sizeof(dp[0]));

        for (int i = 1; i <= c; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] =
                    min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + a[i] - a[i - 1]);
        cout << dp[c][m] << endl;

        // for (int i = 0; i <= c; i++){
        //     for (int j = 0; j <= m; j++)
        //         printf("%5d ",dp[i][j]);
        //     printf("\n");
        // }
    }

#ifdef debug
    printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
    return 0;
}

{% endfold %}