Dreams
NK 1137 (hutc 1036)Pebble Merging(石子合并問題)
http://acm.nankai.edu.cn/p1137.html
http://172.20.16.106/JudgeOnline/showproblem?problem_id=1036
//
7562 liyunsong B Accepted G++ 2009-04-17 12:57:36
#include
<
iostream
>
using
namespace
std;
const
int
N
=
101
;
int
dpmax[
2
*
N][
2
*
N];
//
dpmax[i][j]表示從第i對石子開始連續順時針合并j堆的最大耗費
int
dpmin[
2
*
N][
2
*
N];
//
dpmin[i][j]表示從第i對石子開始連續順時針合并j堆的最小耗費
int
mins[
2
*
N][
2
*
N];
int
maxs[
2
*
N][
2
*
N];
int
num[
2
*
N];
int
main()
{
int
n,i,j,k,r;
while
(cin
>>
n)
{
int
t;
for
(i
=
1
;i
<=
n;i
++
)
scanf(
"
%d
"
,
&
num[i]);
if
(n
==
1
)
{
printf(
"
0\n0\n
"
);
continue
;
}
for
(i
=
1
;i
<=
n;i
++
)
num[i
+
n]
=
num[i];
for
(i
=
1
;i
<=
2
*
n;i
++
)
for
(j
=
1
;j
<=
2
*
n;j
++
)
{
dpmin[i][j]
=
10000000
;
dpmax[i][j]
=
0
;
}
for
(i
=
1
;i
<=
2
*
n;i
++
)
{
dpmin[i][
1
]
=
dpmax[i][
1
]
=
0
;
dpmin[i][i]
=
dpmax[i][i]
=
0
;
mins[i][i]
=
maxs[i][i]
=
num[i];
}
for
(r
=
2
;r
<=
n;r
++
)
//
合并堆數
{
for
(i
=
1
;i
<
2
*
n
-
r
+
1
;i
++
)
//
起點
{
j
=
i
+
r
-
1
;
dpmin[i][j]
=
dpmin[i
+
1
][j]
+
num[i]
+
mins[i
+
1
][j];
mins[i][j]
=
num[i]
+
mins[i
+
1
][j];
dpmax[i][j]
=
dpmax[i
+
1
][j]
+
num[i]
+
maxs[i
+
1
][j];
maxs[i][j]
=
num[i]
+
maxs[i
+
1
][j];
for
(k
=
i
+
1
;k
<
j;k
++
)
{
t
=
mins[i][k]
+
mins[k
+
1
][j]
+
dpmin[i][k]
+
dpmin[k
+
1
][j];
if
(t
<
dpmin[i][j])
{
dpmin[i][j]
=
t;
mins[i][j]
=
mins[i][k]
+
mins[k
+
1
][j];
}
t
=
maxs[i][k]
+
maxs[k
+
1
][j]
+
dpmax[i][k]
+
dpmax[k
+
1
][j];
if
(t
>
dpmax[i][j])
{
dpmax[i][j]
=
t;
maxs[i][j]
=
maxs[i][k]
+
maxs[k
+
1
][j];
}
}
}
}
int
MAX
=
dpmax[
1
][n];
int
MIN
=
dpmin[
1
][n];
for
(i
=
2
;i
<=
n;i
++
)
{
if
(MAX
<
dpmax[i][i
+
n
-
1
])
MAX
=
dpmax[i][i
+
n
-
1
];
if
(MIN
>
dpmin[i][i
+
n
-
1
])
MIN
=
dpmin[i][i
+
n
-
1
];
}
printf(
"
%d\n%d\n
"
,MIN,MAX);
}
return
0
;
}
發表于 2009-04-17 13:05
DreamSky
閱讀(453)
評論(0)
編輯
收藏
引用
所屬分類:
DP
只有注冊用戶
登錄
后才能發表評論。
【推薦】100%開源!大型工業跨平臺軟件C++源碼提供,建模,組態!
相關文章:
hdu 2372 El Dorado
01-package
zju 1883 Tight Words
zju 3201 Tree of Tree
zju 2852 Deck of Cards
hdu 2191 悼念512汶川大地震遇難同胞——珍惜現在,感恩生活
hdu 2765 Recursively Palindromic Partitions
vijos 1313 金明的預算方案
vijos 1133 裝箱問題
vijos 1317 開心的金明
網站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
<
2009年4月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
公告
導航
C++博客
首頁
發新隨筆
發新文章
聯系
聚合
管理
統計
隨筆: 84
文章: 7
評論: 49
引用: 0
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(6)
給我留言
查看公開留言
查看私人留言
隨筆分類
asp相關(3)
(rss)
BFS(8)
(rss)
DFS(7)
(rss)
DP(27)
(rss)
greedy(9)
(rss)
LG(4)
(rss)
Math(7)
(rss)
Others(6)
(rss)
并查集(4)
(rss)
母函數(7)
(rss)
線段樹
(rss)
字典樹(4)
(rss)
隨筆檔案
2009年8月 (3)
2009年5月 (17)
2009年4月 (60)
2009年3月 (4)
文章分類
創作(1)
(rss)
隨感(5)
(rss)
文學(1)
(rss)
文章檔案
2010年12月 (1)
2010年8月 (1)
2009年8月 (1)
2009年5月 (1)
2009年4月 (3)
相冊
烏鎮
原野天地
百事百通
analogy_翻譯_愛詞霸在線詞典
bia菜
CSS學習資料
DB
Feng
Happy峰
Wpl
Xredman
百度
北大ACM
福建師范大學ACM
谷歌
果樹伯伯
杭電ACM
湖州師范學院主頁
精品笑話
綠色軟件
史艷婷
霜天曉角
天津大學ACM
廈門大學ACM
信息學競賽
這是什么
浙大ACM
浙江工商大學ACM
浙江工業大學ACM
浙江林學院ACM
搜索
積分與排名
積分 - 47611
排名 - 473
最新評論
1.?re: hdu 1074 Doing Homework
評論內容較長,點擊標題查看
--guo
閱讀排行榜
1.?hdu 1171 Big Event in HDU(1777)
評論排行榜
1.?hdu 1171 Big Event in HDU(9)
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 DreamSky
亚洲精品无码久久一线
|
亚洲国产精品无码久久久蜜芽
|
97精品伊人久久久大香线蕉
|
久久婷婷色综合一区二区
|
国内高清久久久久久
|
久久亚洲精品成人av无码网站
|
www.久久99
|
免费精品99久久国产综合精品
|
天堂无码久久综合东京热
|
中文字幕日本人妻久久久免费
|
久久综合香蕉国产蜜臀AV
|
国产精品欧美久久久久无广告
|
久久婷婷国产剧情内射白浆
|
99久久久精品
|
久久久久波多野结衣高潮
|
国产成人无码精品久久久久免费
|
亚洲综合久久久
|
午夜视频久久久久一区
|
久久A级毛片免费观看
|
欧美久久天天综合香蕉伊
|
一本色道久久88精品综合
|
狠狠色综合久久久久尤物
|
久久久国产精品网站
|
久久大香萑太香蕉av
|
国产精品久久久久蜜芽
|
99热成人精品免费久久
|
99久久精品国产高清一区二区
|
亚洲精品乱码久久久久久久久久久久
|
久久青青色综合
|
91精品国产91久久久久久蜜臀
|
国产精品无码久久综合
|
久久久无码一区二区三区
|
色婷婷噜噜久久国产精品12p
|
国产成人99久久亚洲综合精品
|
精品视频久久久久
|
亚洲综合婷婷久久
|
亚洲午夜精品久久久久久人妖
|
97久久超碰国产精品旧版
|
国产精品99久久免费观看
|
久久99精品久久久久久久不卡
|
亚洲精品无码成人片久久
|