這題是一個比較簡單的貪心題，不過如果不知道的話，可能會很unhappy了，因為這個是逆向來的，也就是如果你知道了用M塊木板覆蓋的消耗的話，那么你就可以算出用M-1塊木板覆蓋的最小覆蓋，方法就是在M塊木板中找相鄰的兩塊木板相差距離最小的，然后把這兩塊木板連起來，這樣的消耗一定是最小的（這個就不用證明了吧，很明顯的）。根據這個思路，可以比較容易的A掉這題，但是還有一些實現的細節下面看代碼吧。
對于樣例的覆蓋過程是
[3][4][6][8][14][15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14][15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41,42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6][8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6,8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6,8][14,15,16,17][21][25,26,27,30,31][40,41,42,43]
[3,4,6,8][14,15,16,17,21][25,26,27,30,31][40,41,42,43]

code
  6#include <iostream>
 7#include <string.h>
 8using namespace std;
 9/**//*結構體村每個點的數據
10  其中data表示輸入的數據
11  left和right表示他的左右邊
12  有沒有連了其他的木板 
13 */ 
14typedef struct
15{
16    int data;
17    int left,right;
18}Node;
19Node node[202];
20bool b_barn[202];//b_barn[i]表示第i號牛棚有沒有被木板覆蓋 
21int m,s,c;//和題目中的一樣 
22void work()
23{
24      int f_start,f_end,dis;//dis表示最小距離
25      //f_start表示最小距離時的左邊的下標
26      //f_end 表示最小距離時的右邊的下標
27      int count = 0;//用來存最后的結果 
28      int t = c;//表示一開始用c塊木板，也就是一個牛棚一塊 
29      dis = 202;//最大距離，表示無窮 
30      while(t > m)
31        {
32            dis = 202;
33            for(int i = 1;i < c;i++)//循環數組，找相隔最小的，然后連上 
34              {//因為這樣“浪費”的木板最少，也就是能達到最優解 
35                  if(((node[i].data - node[i-1].data) < dis)&&(0 == node[i].left||0 == node[i-1].right))
36                    {//第一個判斷條件很好理解，第二個是表示他們以前沒連過，不然的話，
37                     //會一直找到第一個最小的 ,而忽略了后面的 
38                       dis = node[i].data - node[i-1].data;
39                       f_start = i-1;
40                       f_end = i;
41                      }
42              }
43            for(int i = node[f_start].data+1;i < node[f_end].data;i++)
44              {//將連起來的兩塊木板中間的都置為被覆蓋 
45                 b_barn[i] = true;
46              }
47            node[f_start].right = 1;//標記，也就是這個點的右邊連了其他木板 
48            node[f_end].left = 1;//標記，也就是這個點的左邊連了其他木板
49            t--;//表示木板數減少1 
50         }
51       for(int i = node[0].data;i < node[c-1].data+1;i++)
52        {
53             if(b_barn[i])//通過被標記的數組來算最后的結果 
54                 count++;
55         }
56       printf("%d\n",count);
57}
58int cmp(const void *a,const void *b)
59 {
60      Node * c = (Node *)a;
61      Node * d = (Node *)b;
62      return c->data - d->data;
63}
64int main(void)
65{
66      freopen("barn1.in","r",stdin);
67      freopen("barn1.out","w",stdout);
68      scanf("%d %d %d",&m,&s,&c);
69      memset(b_barn,false,sizeof(b_barn));//初始化數組 
70      for(int i = 0;i < c;i++)
71       {
72          scanf("%d",&node[i].data);
73          node[i].left = node[i].right = 0;//初始化所有的都沒有連過 
74          b_barn[node[i].data] = true;    
75          
76        }
77      qsort(node,c,sizeof(node[0]),cmp);//先排序，使木板有序 
78      work();
79    return 0;
80}
81