问题:
http://ace.delos.com/usacoprob2?a=KIjVa3gj0ap&S=barn1思路:
简单的贪心算法
一直不敢怎么用贪心算法(这题比较好理解)，因为不知道该如何证明其正确性
如何保证每次选择当前最优解最后可以得到整体的最优解？
对于该题:
假设存在M块boards，那么从最左端到最右端(指存在cow的stall)可以存在M-1处gap
最优子结构:
设f(x)表示存在x块boards时的
the minimum number of stalls that must be blocked，那么
f(x) = min(f(x-1) + gap[i] that hasn't been selected)
贪心选择性质: 每次从尚未选择过的gaps中选择最大的gap即可得到最优解(假设为gap[x1], gap[x2], ...gap[x(M-1)])
证明(反证):
假设存在一个最优解，其不包含gap[x(i)]
那么，采用cut-and-paste方法即可证明其不是最优解
代码:
1 /*
2 ID: simplyz2
3 LANG: C
4 TASK: barn1
5 */
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<string.h>
9 #define MAX_LEN 205
10 #define Min(a,b) ((a)<(b) ? (a) : (b))
11 int M, S, C;
12 int rt, stalls[MAX_LEN], diff[MAX_LEN];
13
14 int
15 asc_cmp(const void *arg1, const void *arg2)
16 {
17 return (*(int *)arg1) - (*(int *)arg2);
18 }
19
20 int
21 desc_cmp(const void *arg1, const void *arg2)
22 {
23 return (*(int *)arg2) - (*(int *)arg1);
24 }
25
26 void
27 init()
28 {
29 int i;
30 for(i=0; i<C; i++)
31 scanf("%d", stalls+i);
32 qsort(stalls, C, sizeof(int), asc_cmp);
33 rt = stalls[C-1] - stalls[0] + 1;
34 for(i=1; i<C; i++)
35 diff[i-1] = stalls[i] - stalls[i-1] - 1;
36 qsort(diff, C-1, sizeof(int), desc_cmp);
37 }
38
39 void
40 solve()
41 {
42 int i, up;
43 up = Min(C-1, M-1);
44 for(i=0; i<up; i++)
45 rt -= diff[i];
46 printf("%d\n", rt);
47 }
48
49 int
50 main(int argc, char **argv)
51 {
52 freopen("barn1.in", "r", stdin);
53 freopen("barn1.out", "w", stdout);
54 while(scanf("%d %d %d", &M, &S, &C) != EOF) {
55 init();
56 solve();
57 }
58 return 0;
59 }