Posted on 2009-03-17 17:09
superman 阅读(76)
评论(0) 编辑 收藏 引用 所属分类:
USACO
code 1
1 #include <iostream>
2
3 using namespace std;
4
5 class Interval
6 {
7 public:
8 int length, start;
9
10 bool operator < (const Interval & i) const
11 {
12 return length < i.length;
13 }
14 } interval[200];
15
16 int main()
17 {
18 freopen("barn1.in", "r", stdin);
19 freopen("barn1.out", "w", stdout);
20
21 int n; //the maximum number of boards that can be purchased
22 int m; //the number of cows in the stalls
23 int x[200]; //the number of each occupied stall
24
25 cin >> n >> m >> m;
26 for (int i = 0; i < m; i++)
27 cin >> x[i];
28
29 sort(x, x + m);
30
31 for (int i = 0; i < m - 1; i++)
32 {
33 interval[i].start = x[i];
34 interval[i].length = x[i + 1] - x[i] - 1;
35 }
36
37 sort(interval, interval + m - 1);
38
39 int ans = x[m - 1] - x[0] + 1;
40
41 n -= 1;
42 for (int i = m - 2; i >= 0 && n; i--)
43 ans -= interval[i].length, n--;
44
45 cout << ans << endl;
46
47 return 0;
48 }
49
code 2
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("barn1.in", "r", stdin);
8 freopen("barn1.out", "w", stdout);
9
10 int n, m, x[500], f[500][500];
11
12 cin >> n >> m >> m;
13 for (int i = 1; i <= m; i++)
14 cin >> x[i];
15
16 sort(x + 1, x + 1 + m);
17
18 f[1][1] = 1;
19 for (int i = 2; i <= m; i++)
20 f[1][i] = f[1][i - 1] + x[i] - x[i - 1];
21 for (int i = 2; i <= min(n, m); i++)
22 for (int j = i; j <= m; j++)
23 {
24 f[i][j] = 65535;
25 for (int k = i; k <= j; k++)
26 f[i][j] <?= f[i - 1][k - 1] + (x[j] - x[k] + 1);
27 }
28
29 cout << f[min(n, m)][m] << endl;
30
31 return 0;
32 }
33