問題:
http://ace.delos.com/usacoprob2?a=KIjVa3gj0ap&S=barn1思路:
簡單的貪心算法
一直不敢怎么用貪心算法(這題比較好理解)，因為不知道該如何證明其正確性
如何保證每次選擇當前最優(yōu)解最后可以得到整體的最優(yōu)解？
對于該題:
假設(shè)存在M塊boards，那么從最左端到最右端(指存在cow的stall)可以存在M-1處gap
最優(yōu)子結(jié)構(gòu):
設(shè)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)
貪心選擇性質(zhì): 每次從尚未選擇過的gaps中選擇最大的gap即可得到最優(yōu)解(假設(shè)為gap[x1], gap[x2], ...gap[x(M-1)])
證明(反證):
假設(shè)存在一個最優(yōu)解，其不包含gap[x(i)]
那么，采用cut-and-paste方法即可證明其不是最優(yōu)解
代碼:
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 }