<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
Description
在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。 
给出:可能买到的木板最大的数目M(1<=M<=50);牛棚的总数S(1<=S<=200); 牛棚里牛的总数C(1<=C<=S);和牛所在的牛棚的编号stall_number(1<=stall_number<=S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。
</div><div class="part" title="Input">
1行: M，S和C(用空格分开) 
2到C+1行:每行包含一个整数，表示牛所占的牛棚的编号。
</div><div class="part" title="Output">
单独的一行包含一个整数表示所需木板的最小总长度。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
<p>4 50 18<br>
3<br>
4<br>
6<br>
8<br>
14<br>
15<br>
16<br>
17<br>
21<br>
25<br>
26<br>
27<br>
30<br>
31<br>
40<br>
41<br>
42<br>
43</p>
</div><div class="output part" title="Sample Output">
<p>25</p>
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>这道题有多种不同的思路</p>
<h2 id="heading-2">贪心</h2>
<p>首先假定我们用一个木板拦住所有的牛,当我们有多于一个木板的时候,我们的任务就是选一个<strong>最大的区间</strong>,从这里把木板拆成两个</p>
<p>当有多个木板时同理,不停寻找最大的区间即可</p>
<p>细节比较多,可以把中间变量输出出来进行测试</p>
<p><strong>需要特别注意的是: 牛所在的牛栏并不是有序输出的,同时存在没有牛和木板比牛的情况</strong></p>
<h2 id="heading-3">动态规划</h2>
<p>动态规划最重要的是转移方程</p>
<p>可以看出自变量的应该是木板数和牛栏数,也即有:<br>
<code>dp(i,j)</code> 表示前i个牛栏使用j个木板所需要的最小木板总长度</p>
<p>那么就可以看出在已经有<code>dp(i-1,j)</code>的情况下,又加入一个新的牛栏(有牛),存在两种处理方案：</p>
<ul>
<li>用一块新的木板 <code>dp(i-1,j-1)+1</code></li>
<li>延长上一块木板 <code>dp(i-1,j)+a[i]-a[i-1]</code></li>
</ul>
<p>也即 <code>dp(i,j) = min( dp(i-1,j-1)+1, dp(i-1,j)+a[i]-a[i-1] )</code></p>
<p>然后需要处理的就是边界条件<br>
按照实际含义来想,<code>dp(0,k)</code> 表示0个牛栏需要的木板数,显然应该是0<br>
而 <code>dp(k,0)</code> (k!=0) 表示没有木板的情况下,拦住k个有牛的牛栏,应该是无穷大</p>
<p>综上:<br>
{% raw %}$<br>
dp(i,j) = \left{\begin{matrix}<br>
0                                           &amp; i=0\<br>
INF                                         &amp; i \neq 0,j=0\<br>
min(dp(i-1,j-1)+1,dp(i-1,j)+a[i]-a[i-1])    &amp; 其他<br>
\end{matrix}\right.<br>
${% endraw %}</p>
<h1 id="heading-4">代码</h1>
<h2 id="heading-5">贪心</h2>
<p>{% fold 点击显/隐代码 %}```cpp 修理牛棚(贪心) <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
/<em>/<br>
#define debug<br>
#include <ctime><br>
//</em>/<br>
#include <algorithm><br>
#include <cstdio><br>
#include <cstring><br>
#include <iostream><br>
using namespace std;</p>
<p>const int maxn = 205;<br>
int a[maxn], b[maxn];<br>
int m, s, c;</p>
<p>int main() {<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>while (cin &gt;&gt; m &gt;&gt; s &gt;&gt; c) {
    for (int i = 0; i &lt; c; i++)
        cin &gt;&gt; a[i];
    sort(a,a+c);
    if (c == 0 || m &gt;= c ) {
        cout &lt;&lt; c &lt;&lt; endl;
    } else {
        for (int i = 0; i &lt; 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&lt;&lt;ans&lt;&lt;endl;
        for (int i = 0; i &lt; m - 1; i++) {
            // cout&lt;&lt;b[c-1-i]&lt;&lt;endl;
            ans -= b[c - 2 - i];
        }
        cout &lt;&lt; ans &lt;&lt; endl;
    }
}
</code></pre>
<p>#ifdef debug<br>
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);<br>
#endif<br>
return 0;<br>
}</p>
<pre style="background-color:#fff">{% endfold %}

## 动态规划
{% fold 点击显/隐代码 %}```cpp 修理牛棚(dp) https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include &lt;ctime&gt;
//*/
#include &lt;algorithm&gt;
#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;iostream&gt;
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(&#34;in.txt&#34;, &#34;r&#34;, stdin);
    int START = clock();
#endif
    cin.tie(0);
    cin.sync_with_stdio(false);

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

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

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

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

#ifdef debug
    printf(&#34;Time:%.3fs.\n&#34;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
    return 0;
}
</pre><p>{% endfold %}</p>

AOJ 890.修理牛棚