久久精品水蜜桃av综合天堂,久久天堂电影网,青青草原1769久久免费播放

堅(jiān)信：勤能補(bǔ)拙

PKU 1260 Pearls

問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1260

思路:
簡(jiǎn)單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 閱讀(152) 評(píng)論(0) 編輯收藏引用所屬分類(lèi): C_動(dòng)態(tài)規(guī)劃

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

A Za, A Za, Fighting...

PKU 1260 Pearls

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆分類(lèi)

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜