Posted on 2008-04-27 22:09
superman 阅读(415)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1196 C++ 00:00.04 1020K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, chain = 0;
9 while(cin >> n >> m)
10 {
11 if(n == 0 && m == 0)
12 break;
13
14 int p[201];
15 for(int i = 1; i <= n; i++)
16 cin >> p[i];
17
18 int w[201][201] = {0};
19 for(int i = 1; i <= n; i++)
20 for(int j = 1; j <= n; j++)
21 for(int k = i; k <= j; k++)
22 w[i][j] += abs(p[k] - p[(i + j) / 2]);
23
24 int opt[31][201];
25
26 for(int i = 1; i <= n; i++)
27 opt[1][i] = w[1][i];
28
29 for(int i = 2; i <= m; i++)
30 for(int j = i; j <= n; j++)
31 {
32 opt[i][j] = INT_MAX;
33 for(int k = i - 1; k < j; k++)
34 opt[i][j] <?= (opt[i - 1][k] + w[k + 1][j]);
35 }
36 chain++;
37 cout << "Chain " << chain << endl
38 << "Total distance sum = " << opt[m][n] << endl << endl;
39 }
40
41 return 0;
42 }
43