superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1563 - Pearls

Posted on 2008-06-05 21:44 superman 阅读(267) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理