Posted on 2008-06-05 21:44
superman 阅读(268)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1563 C++ 00:00.01 920K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int c, n;
9 struct { int need, price; } pearl[101];
10
11 cin >> c;
12 while(c--)
13 {
14 cin >> n;
15 for(int i = 1; i <= n; i++)
16 cin >> pearl[i].need >> pearl[i].price;
17
18 int sum[101][101] = { 0 };
19 for(int i = 1; i <= n; i++)
20 for(int j = i; j <= n; j++)
21 sum[i][j] = sum[i][j - 1] + pearl[j].need;
22
23 int opt[101][101] = { 0 };
24
25 for(int i = 1; i <= n; i++)
26 opt[1][i] = (sum[1][i] + 10) * pearl[i].price;
27
28 for(int i = 2; i <= n; i++)
29 for(int j = 1; j <= n; j++)
30 {
31 opt[i][j] = INT_MAX;
32 for(int k = 1; k <= j; k++)
33 opt[i][j] <?= opt[i - 1][k - 1] + (sum[k][j] + 10) * pearl[j].price;
34 }
35 cout << opt[n][n] << endl;
36 }
37
38 return 0;
39 }
40