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ǎ崽
国产一区二区久久久
|
伊人久久成人成综合网222
|
久久精品国产亚洲AV忘忧草18
|
久久精品一区二区影院
|
久久亚洲精品无码aⅴ大香
|
无码AV中文字幕久久专区
|
亚洲嫩草影院久久精品
|
一本久久精品一区二区
|
久久九九青青国产精品
|
久久精品青青草原伊人
|
99久久精品免费看国产免费
|
综合人妻久久一区二区精品
|
中文字幕亚洲综合久久2
|
狠狠综合久久综合88亚洲
|
日本久久久精品中文字幕
|
亚洲精品美女久久777777
|
国产精品免费久久久久电影网
|
成人午夜精品无码区久久
|
久久免费视频一区
|
中文精品久久久久国产网址
|
熟妇人妻久久中文字幕
|
久久精品一区二区三区中文字幕
|
久久超乳爆乳中文字幕
|
久久天天躁狠狠躁夜夜av浪潮
|
人妻精品久久久久中文字幕69
|
狠狠色综合久久久久尤物
|
日本欧美久久久久免费播放网
|
狠狠精品久久久无码中文字幕
|
久久久久人妻一区精品色
|
国产偷久久久精品专区
|
一本一道久久a久久精品综合
|
亚洲成av人片不卡无码久久
|
天天爽天天爽天天片a久久网
|
浪潮AV色综合久久天堂
|
亚洲狠狠婷婷综合久久蜜芽
|
久久久久久久91精品免费观看
|
久久久精品国产Sm最大网站
|
国内精品免费久久影院
|
国内精品久久久久久久久
|
久久se这里只有精品
|
久久er国产精品免费观看8
|