A Crazy Man
ACM
C++博客
首頁
新隨筆
聯(lián)系
聚合
管理
隨筆-72 評論-126 文章-0 trackbacks-0
狀態(tài)DP~
http://acm.sgu.ru/problem.php?contest=0&problem=222
這是入門題,數(shù)據(jù)較大,需要記憶化搜索
http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
上題的提高版,不過數(shù)據(jù)超小,爆搜都能過
http://acm.sgu.ru/problem.php?contest=0&problem=223
先要預處理出一行中的全部可行狀態(tài)~
然后DP的時候巧妙的運用位運算進行狀態(tài)的判斷和轉(zhuǎn)移
狀態(tài)dp中位運算的巧妙運用會大幅度提高程序的效率和帥氣程度
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
非常經(jīng)典的狀態(tài)DP,由于攻擊范圍是兩格,所以要保持兩個狀態(tài),有人用三進制壓縮,我覺得太煩了(不能使用飄逸的位運算)
但是[101][2^10][2^10]得狀態(tài)太大,考慮到2^10中有很多情況是不可到達的
計算下當m=10的時候最多60個合法狀態(tài),所以我開了[101][60][60]的數(shù)組記憶化DP過了
http://acm.hdu.edu.cn/showproblem.php?pid=2640
teddy大牛的題目,和上題差不多,不過不能重疊放,所以處理比上題煩很多
同樣2^8里有很多不可到達的情況,最多之有13種
所以我開[101][13][13]的數(shù)組15ms就過了,哈哈
這就好像是
兩次狀態(tài)壓縮
最近的DP題目感覺到
把很多不可到達的狀態(tài)壓縮掉
效率會提高超多~也可能讓程序從TLE MLE變成AC~
http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
http://acm.hdu.edu.cn/showproblem.php?pid=1400
這道其實很簡單,先預處理出當前狀態(tài)s1到下一狀態(tài)的可能值s2,hash[1<<m,1<<m]記錄,m為較小值
dp[0][(1<<m)-1] = 1
然后經(jīng)過n*(1<<m)*(1<<m)的循環(huán)得出結(jié)果dp[n][(1<<m)-1]
http://acm.sgu.ru/problem.php?contest=0&problem=223
兩種磚塊,除了預處理的時候狀態(tài)多點,有7種分支,其他的都和上一題一樣
(主意一個狀態(tài)到另一個狀態(tài)可能會有多種情況,hash的時候要用++而不是true false)
http://acm.hdu.edu.cn/showproblem.php?pid=2280
要求用最少的1鋪滿所有的空格,其中3是沒用的(可以用兩個5代替),化簡之后使用的方塊和上一題一樣,一樣的預處理后
dp求出最少的1
http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
http://acm.hdu.edu.cn/showproblem.php?pid=2696
http://acm.hdu.edu.cn/showproblem.php?pid=2442
http://acm.hdu.edu.cn/showproblem.php?pid=1755
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=1668
http://acm.hdu.edu.cn/showproblem.php?pid=2518
http://acm.hdu.edu.cn/showproblem.php?pid=1666
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=2315
posted on 2009-07-12 16:40
shǎ崽
閱讀(2498)
評論(0)
編輯
收藏
引用
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
網(wǎng)站導航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
QQ:477627586 Email:notnolysuccess@gmail.com
<
2009年7月
>
日
一
二
三
四
五
六
28
29
30
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
31
1
2
3
4
5
6
7
8
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(4)
給我留言
查看公開留言
查看私人留言
隨筆檔案
(72)
2009年11月 (1)
2009年9月 (1)
2009年8月 (1)
2009年7月 (3)
2009年6月 (1)
2009年5月 (6)
2009年4月 (11)
2009年3月 (28)
2009年2月 (20)
links
FZU大大AekdyCoin
偶像hhanger
啟蒙老師LCY
神牛matrix67
搜索
最新評論
1.?re: 半年AC生涯,僅以此文紀念
膜拜巨巨
--zhaop
2.?re: 概率題總匯
概率題感覺還沒入門T T,求看zjut大牛的文章,感謝樓主。lmh463896910@gmail.com
--Plumrain
3.?re: 神奇的舞蹈~~Dancing_Links[未登錄]
HDOJ:1530,用dancing links,lz能不能再講詳細點或者求代碼?
--柳晴
4.?re: 概率題總匯
我也想看浙大牛人文章,可不可以給我也發(fā)一份776593191@qq.com。跪謝
--meander
5.?re: 樹形DP
評論內(nèi)容較長,點擊標題查看
--隨心小亞
6.?re: 概率題總匯
傻仔大哥,我也想看浙大牛人文章,可不可以給我也發(fā)一份
462039091@qq.com
--song
7.?re: 概率題總匯
matrix,yms@gmail.com 謝謝啦
--求 zjut一位大牛的文章
8.?re: 八數(shù)碼的A*算法
http://www.acmwiki.com
歡迎光臨
--acm百科網(wǎng)
9.?re: 半年AC生涯,僅以此文紀念
你不是一般的crazy~~
--Kkxhappy123
10.?re: 半年AC生涯,僅以此文紀念
羨慕你的生活,話說我的AC世界就悲劇多了。。
--kisa
閱讀排行榜
1.?神奇的舞蹈~~Dancing_Links(11480)
2.?樹形DP(6175)
3.?hdoj1006~~Tick and Tick(5296)
4.?概率題總匯(3932)
5.?PKU——DP專輯(3718)
6.?半年AC生涯,僅以此文紀念(3679)
7.?浙江省歷年省賽題+解析(3409)
8.?狀態(tài)DP~(2498)
9.?神奇的matrix運算(2298)
10.?圖論~~要大干一場了--Author McFn(2215)
評論排行榜
1.?半年AC生涯,僅以此文紀念(19)
2.?神奇的舞蹈~~Dancing_Links(13)
3.?概率題總匯(10)
4.?神奇的matrix運算(8)
5.?hdoj1271解題報告(8)
6.?HDOJ1074~~Doing Homework解題報告(7)
7.?hdoj1430~~魔板~~解題報告(5)
8.?一些計算幾何基礎公式(含5題及相關(guān)模板)(4)
9.?圖論~~要大干一場了--Author McFn(4)
10.?PKU——DP專輯(4)
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 shǎ崽
99国产欧美久久久精品蜜芽
|
久久伊人精品青青草原日本
|
久久天天躁狠狠躁夜夜96流白浆
|
污污内射久久一区二区欧美日韩
|
18岁日韩内射颜射午夜久久成人
|
浪潮AV色综合久久天堂
|
青青草原综合久久
|
久久久国产视频
|
嫩草影院久久99
|
久久香综合精品久久伊人
|
久久久国产精品福利免费
|
欧美黑人激情性久久
|
天天久久狠狠色综合
|
久久天天躁夜夜躁狠狠
|
久久精品水蜜桃av综合天堂
|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
亚洲国产成人久久精品影视
|
伊人色综合久久天天网
|
999久久久免费国产精品播放
|
99久久国产宗和精品1上映
|
国产成人AV综合久久
|
97久久超碰国产精品2021
|
久久91精品国产91
|
精品国产热久久久福利
|
国产亚洲综合久久系列
|
中文字幕久久精品无码
|
久久午夜无码鲁丝片午夜精品
|
久久亚洲欧美国产精品
|
伊人久久大香线蕉av不变影院
|
久久国产V一级毛多内射
|
久久66热人妻偷产精品9
|
国产精品久久久久久五月尺
|
伊人久久五月天
|
欧美精品九九99久久在观看
|
色综合久久久久综合99
|
性做久久久久久久久
|
久久无码国产专区精品
|
久久国产色av免费看
|
久久精品人人做人人爽电影
|
亚洲AV无码久久精品成人
|
久久精品一本到99热免费
|