狠狠色婷婷综合天天久久丁香,91精品国产91久久,久久综合香蕉国产蜜臀AV

堅信：勤能補拙

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 閱讀(157) 評論(0) 編輯收藏引用所屬分類: C_動態規劃

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: PKU 3670 Eating Together PEARL 硬幣找零(動態規劃) USACO Broken Necklace PKU 1456 Supermarket PKU 1260 Pearls PKU 1179 Polygon PKU 1157 Little Shop of Flowers [最長上升子序列 nlogn] PKU 1631 Bridging signals [最長上升子序列 n^2]PKU 1887 Testing the CATCHER / PKU 2533 Longest Ordered Subsequence PKU 2192 Zipper

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

A Za, A Za, Fighting...

PKU 1260 Pearls

導航

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜