A Za, A Za, Fighting...

坚信：勤能补拙

PKU 1260 Pearls

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1260

思路:
简单DP，但是就是想不到...

代码:
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAX_LEN 101
 5 #define INF 0x7FFFFFFF
 6 #define min(a,b) ((a)<(b) ? (a) : (b))
 7 int num[MAX_LEN], price[MAX_LEN];
 8 int sum[MAX_LEN]; /* aux */
 9 int table[MAX_LEN];
10 int c;
11 
12 /*
13  * f[i] represent the lowest possible price needed to buy list[1..i], so:
14  *      f[i] = min (f[k] + (num[k+1]++num[i]+10)*price[i]), 0<=k<i-1
15  */
16 int
17 dp()
18 {
19     int i, k, tmp;
20     sum[0] = 0;
21     for(i=1; i<=c; i++)
22         sum[i] = sum[i-1]+num[i];
23     table[0] = 0;
24     for(i=1; i<=c; i++) {
25         table[i] = INF;
26         for(k=0; k<=i-1; k++) {
27             tmp = table[k] + (sum[i]-sum[k]+10)*price[i];
28             table[i] = min(table[i], tmp);
29         }
30     }
31     return table[c];
32 }
33 
34 int
35 main(int argc, char **argv)
36 {
37     int i, tests;
38     scanf("%d", &tests);
39     while(tests--) {
40         scanf("%d", &c);
41         for(i=1; i<=c; i++)
42             scanf("%d %d", num+i, price+i);
43         printf("%d\n", dp());
44     }
45 }

posted on 2010-08-18 09:33 simplyzhao 阅读(135) 评论(0)  编辑 收藏 引用 所属分类: C_动态规划


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


导航

<2010年10月>
日一二三四五六
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜