解題報告
uva 12583 可持久化treap
摘要: 對一個字符串S(初始為空)，有Q次操作(Q<=50,000)，操作分三種：
1. 在某個位置p后面插入一個長度不大于100的字符串。
2. 刪除一段字符[l,r]
3. 輸出在第k次操作時，字符串(S_l ... S_r) 插入的字符不超過1,000,000個。
閱讀全文
posted @
2013-03-19 22:15 西月弦 閱讀(1588) |
評論 (1) 編輯
動態(tài)規(guī)劃求解背包類問題(更新中...)
摘要: 我理解的背包類問題，大概有兩類：
(1) 在N組物品中，挑選出M個，使得某些性質(zhì)最優(yōu)。
(2) 在N組物品中，挑選出M個，求并符合某條件的方案數(shù)。
閱讀全文
posted @
2012-12-03 13:40 西月弦 閱讀(455) |
評論 (0) 編輯
codeforces 145C DP+數(shù)論
摘要: 給長度為n的數(shù)列，(n<1e5)。讓你求選擇沒有相同的lucky number的子序列的方法數(shù) mod 1e9+7。
閱讀全文
posted @
2012-11-30 18:39 西月弦 閱讀(481) |
評論 (0) 編輯
topcoder srm 561 div1
摘要: topcoder srm 561 div1
閱讀全文
posted @
2012-11-21 16:02 西月弦 閱讀(534) |
評論 (3) 編輯
2012亞洲區(qū)成都現(xiàn)場賽原創(chuàng)題解
摘要: 2012亞洲區(qū)成都現(xiàn)場賽原創(chuàng)題解
閱讀全文
posted @
2012-11-17 23:04 西月弦 閱讀(1148) |
評論 (6) 編輯
codeforces #148 (坑。。)
摘要: codeforces #148 (坑。。)
閱讀全文
posted @
2012-11-05 20:25 西月弦 閱讀(445) |
評論 (0) 編輯
2012天津賽區(qū)原創(chuàng)題解
摘要: 題目連接
http://acm.hdu.edu.cn/search.php?field=problem&key=2012%20Asia%20Tianjin%20Regional%20Contest&source=1&searchmode=source
閱讀全文
posted @
2012-10-30 00:07 西月弦 閱讀(1023) |
評論 (8) 編輯
codeforces #147 div2
摘要: codeforces #147 div2
閱讀全文
posted @
2012-10-28 16:01 西月弦 閱讀(432) |
評論 (3) 編輯
poj 3415 SAM
摘要: 詢問兩個長度為100,000的字符串，不小于k的公共子串有多少個。
閱讀全文
posted @
2012-10-25 19:23 西月弦 閱讀(577) |
評論 (0) 編輯
topcoder srm 558 div1
摘要: topcoder srm 558 div1
閱讀全文
posted @
2012-10-24 16:22 西月弦 閱讀(259) |
評論 (0) 編輯
codeforces #146 div1
摘要: codeforces #146 div1
閱讀全文
posted @
2012-10-24 14:13 西月弦 閱讀(568) |
評論 (2) 編輯
topcoder srm 557 div1
摘要: topcoder srm 557 div1
閱讀全文
posted @
2012-10-18 14:00 西月弦 閱讀(474) |
評論 (0) 編輯
codeforces #145
摘要: codeforces #145
閱讀全文
posted @
2012-10-17 13:47 西月弦 閱讀(645) |
評論 (1) 編輯
poj 2949 spfa求正環(huán)
摘要: 題目描述：
有N個串，兩個尾首兩個字母相同的串可以連接。求最大均值圈。
閱讀全文
posted @
2012-10-10 19:32 西月弦 閱讀(313) |
評論 (0) 編輯
fzu 2042 數(shù)位DP
摘要: 題目描述：
給出五個數(shù)（不超過2^63-1），讓你求下面代碼的sum值
for(ll i = a; i <= b; i++)
for(ll j = c; j<= d; j++)
if((i ^ j) > e)
sum += i^j;
閱讀全文
posted @
2012-10-10 14:56 西月弦 閱讀(439) |
評論 (0) 編輯
codeforces #139
摘要: codeforces #139
閱讀全文
posted @
2012-10-08 15:00 西月弦 閱讀(237) |
評論 (0) 編輯
codeforces #140
摘要: codeforces #140
閱讀全文
posted @
2012-10-07 16:10 西月弦 閱讀(562) |
評論 (10) 編輯
codeforces #141
摘要: codeforces #141
閱讀全文
posted @
2012-10-04 00:51 西月弦 閱讀(285) |
評論 (0) 編輯
codeforces #142
摘要: codeforces #142
閱讀全文
posted @
2012-10-03 14:47 西月弦 閱讀(394) |
評論 (0) 編輯
topcoder srm 555 div1 [pratice]
摘要: topcoder srm 555 div1 [pratice]
閱讀全文
posted @
2012-10-02 23:42 西月弦 閱讀(272) |
評論 (0) 編輯
codeforces #137 div2
摘要: codeforces #137 div2
閱讀全文
posted @
2012-09-11 21:39 西月弦 閱讀(395) |
評論 (3) 編輯
hdu 4285 插頭DP
摘要: 求12×12矩陣上的互不嵌套的k個哈密頓回路的方案數(shù)。
閱讀全文
posted @
2012-09-10 21:09 西月弦 閱讀(1164) |
評論 (5) 編輯
zoj 1063 廣搜
摘要: 狗狗四十題第六題
閱讀全文
posted @
2012-09-10 11:33 西月弦 閱讀(240) |
評論 (0) 編輯
zoj 1021 遞歸
摘要: 狗狗四十題第一題
閱讀全文
posted @
2012-09-03 19:58 西月弦 閱讀(299) |
評論 (0) 編輯
codeforces #136 div1
摘要: codeforces #136 div1
閱讀全文
posted @
2012-09-01 12:57 西月弦 閱讀(609) |
評論 (7) 編輯
topcoder srm 552 div1 比賽小記
摘要: topcoder srm 552 div1 比賽小記
閱讀全文
posted @
2012-08-17 13:17 西月弦 閱讀(400) |
評論 (1) 編輯
hdu 4127 迭代加深搜索
摘要: 玩flood-it游戲, 一個8*8的帶6種顏色的格子. 每次占領(lǐng)與已占領(lǐng)的聯(lián)通塊相鄰的聯(lián)通塊, 問最少幾次可以全部占領(lǐng)完. 第一次占領(lǐng)左上角.
閱讀全文
posted @
2012-08-15 20:56 西月弦 閱讀(425) |
評論 (0) 編輯
codeforces #133 div2
摘要: codeforces #133 div2
閱讀全文
posted @
2012-08-15 16:25 西月弦 閱讀(270) |
評論 (0) 編輯
codeforces 213E 多項(xiàng)式哈希+線段樹
摘要: 給兩個長度為200,000的全排列a,b. 尋找整數(shù)k的個數(shù),使a的每個數(shù)加上k以后,是b的子序列.
閱讀全文
posted @
2012-08-10 22:54 西月弦 閱讀(487) |
評論 (0) 編輯
codeforces #132 div2
摘要: codeforces #132 div2
閱讀全文
posted @
2012-08-10 10:42 西月弦 閱讀(345) |
評論 (0) 編輯
codeforces 213D 計(jì)算幾何
摘要: 要求一筆劃畫出N(N<100)個五角形，輸出方案(畫的軌跡)。
閱讀全文
posted @
2012-08-06 22:25 西月弦 閱讀(293) |
評論 (0) 編輯
hdu 4116 計(jì)算幾何 + 掃描線
摘要: 在無限平面上有N(N<1,000)個圓。問一條直線最多可以“穿過”幾個圓，相切也算。
閱讀全文
posted @
2012-08-06 14:58 西月弦 閱讀(1250) |
評論 (0) 編輯
codeforces 212D 線段樹 + 棧的應(yīng)用
摘要: 給1,000,000個數(shù)，大小不超過10^9。詢問1,000,000次，長度為k的區(qū)間最小值的期望。
閱讀全文
posted @
2012-08-05 19:57 西月弦 閱讀(332) |
評論 (0) 編輯
hdu 3712 計(jì)算幾何
摘要: 給一個點(diǎn)光源(x0,y0)，向(x1,y1)處發(fā)射射線。p0,p1,p2三個點(diǎn)是三棱鏡，折射率為n。求最后光線與x軸的交點(diǎn)。
閱讀全文
posted @
2012-08-05 14:35 西月弦 閱讀(465) |
評論 (0) 編輯
hdu 4060 二分圖最小點(diǎn)覆蓋
摘要: 由于題目描述過于imba，這里直接給出鏈接吧
http://acm.hdu.edu.cn/showproblem.php?pid=4060
閱讀全文
posted @
2012-08-04 06:14 西月弦 閱讀(374) |
評論 (0) 編輯
hdu 3694 計(jì)算幾何
摘要: 求四個點(diǎn)的費(fèi)馬點(diǎn)與這四個點(diǎn)的距離和。
閱讀全文
posted @
2012-08-03 16:26 西月弦 閱讀(188) |
評論 (0) 編輯
codeforces #131 div1
摘要: codeforces #131 div1
閱讀全文
posted @
2012-08-03 15:36 西月弦 閱讀(281) |
評論 (0) 編輯
hdu 3683 極大極小過程 + 搜索
摘要: 在一個15*15的棋盤上下五子棋。3步之內(nèi)誰能贏。
閱讀全文
posted @
2012-07-30 21:31 西月弦 閱讀(316) |
評論 (0) 編輯
hdu 4126 最小生成樹 + 樹形DP + 優(yōu)先級隊(duì)列
摘要: 求N<3,000個點(diǎn)的稠密圖的最小生成樹的每條邊的最佳替換邊。
閱讀全文
posted @
2012-07-30 13:46 西月弦 閱讀(413) |
評論 (0) 編輯
hdu 4305 計(jì)算幾何 + 高斯消元求行列式 + 逆元
摘要: 平面上有N<300個點(diǎn)。每個兩個點(diǎn)如果距離小于R且之間沒有共線的另一個點(diǎn)，則這兩點(diǎn)之間有一條邊。求這個圖的生成樹的個數(shù)mod 10007。
閱讀全文
posted @
2012-07-29 22:29 西月弦 閱讀(440) |
評論 (0) 編輯
codeforces 212C 遞推
摘要: 有一個長度為100的只含A和B的環(huán)行串。如果這個串含有AB，那么就變?yōu)锽A。 給一個串，問有多少種串可以變?yōu)檫@個串。
閱讀全文
posted @
2012-07-29 18:41 西月弦 閱讀(364) |
評論 (0) 編輯
codeforces 204E 后綴數(shù)組+線段樹
摘要: 給N個串(N<100,000)，總長不超過100,000。對于每個串，求至少在其他k個串中作為子串出現(xiàn)過的子串個數(shù)。
閱讀全文
posted @
2012-07-26 10:20 西月弦 閱讀(766) |
評論 (1) 編輯
codeforces #130 div2
摘要: codeforces #130 div2
閱讀全文
posted @
2012-07-24 17:23 西月弦 閱讀(313) |
評論 (2) 編輯
hdu 4117 AC自動機(jī) + DP
摘要: 有N(N<20,000)個只含有小寫字母的字符串，總長不超過300,000，每個字符串Si有權(quán)值Vi?，F(xiàn)在讓你刪除一些字符串，滿足對于相鄰的串，前一個串是后一個串的子串。求最大權(quán)值和。
閱讀全文
posted @
2012-07-23 12:52 西月弦 閱讀(1355) |
評論 (2) 編輯
codeforces 212E 樹形DP + 背包
摘要: 題目描述：
一棵N(N<5,000)個節(jié)點(diǎn)的樹，染兩種顏色，不同顏色不能相鄰且要給盡可能多的節(jié)點(diǎn)染色。求顏色A和顏色B可能的染色節(jié)點(diǎn)個數(shù)。
閱讀全文
posted @
2012-07-21 22:47 西月弦 閱讀(293) |
評論 (0) 編輯
codeforces 204D 動態(tài)規(guī)劃
摘要: 有一個長度為n(n<1,000,000)的字符串A。有三種字符，'B','W','X'?，F(xiàn)在讓你將所有的X要么變成B，要么變成W，構(gòu)造字符串，使得其存在a<=b
閱讀全文
posted @
2012-07-21 19:13 西月弦 閱讀(342) |
評論 (0) 編輯
codeforces 200A 并查集
摘要: 給一個大小為n*m(n,m < 2000)的棋盤，有k(K<100,000)次操作。每次在位置（x,y）加入一個點(diǎn)，如果x,y已經(jīng)有點(diǎn)了，那么加入的點(diǎn)需要滿足：
1. 與x,y的曼哈頓距離最近。
2. 如果滿足條件1的點(diǎn)有多個，那么要求x最小。
3. 如果滿足條件2的點(diǎn)有多個，那么要求y最小。
閱讀全文
posted @
2012-07-21 15:02 西月弦 閱讀(322) |
評論 (0) 編輯
hdu 4008 樹形DP + LCA
摘要: 題目描述：
給一顆結(jié)點(diǎn)數(shù)為(100,000)的樹，最多詢問100,000次。每次詢問對兩個結(jié)點(diǎn)X,Y，以X為根，Y的最小標(biāo)號的孩子，Y的最小標(biāo)號的后代。
閱讀全文
posted @
2012-07-17 10:53 西月弦 閱讀(502) |
評論 (0) 編輯
codeforces #127 div1
摘要: codeforces #127 div1
閱讀全文
posted @
2012-06-30 02:49 西月弦 閱讀(547) |
評論 (0) 編輯
hdu 4087 仿射幾何 + 矩陣乘法
摘要: 定義一種變換向量的語言，其語法有這么幾種：
1. translate tx ty tz 功能：(x,y,z) = (x+tx,y+ty,z+tz)
2. scale a b c 功能：(x,y,z) = (ax,by,cz)
3. rotate tx ty tz angle 功能：讓x,y,z以tx,ty,tz為軸逆時針旋轉(zhuǎn)angle。
4. rotate k .... end 功能： 重復(fù)執(zhí)行...k次
給若干個向量，輸出對應(yīng)的變換后的向量。
閱讀全文
posted @
2012-06-24 16:01 西月弦 閱讀(423) |
評論 (1) 編輯
codeforces 198C 二分答案 + 計(jì)算幾何
摘要: 有個星球起始位置是（xp,yp），繞原點(diǎn)以速度Vp做勻速圓周運(yùn)動。不明物體起始位置（x,y），速度為V(V>Vp)。這個物體可以隨意移動，但是任何時刻與原點(diǎn)的距離不能小于r。請問這個物體想要與星球位置重合的最少時間是多少？
閱讀全文
posted @
2012-06-23 19:26 西月弦 閱讀(496) |
評論 (0) 編輯
hdu 3727 主席樹+ 線段樹
摘要: 對一個序列進(jìn)行維護(hù)，要求支持四種操作：
1. 在結(jié)尾加入一個數(shù)。
2. 詢問區(qū)間第K大的數(shù)
3. 詢問大小為X的數(shù)在序列中的排名
4. 詢問第K大的數(shù)
閱讀全文
posted @
2012-06-21 15:47 西月弦 閱讀(1132) |
評論 (4) 編輯
bzoj 2653 二分枚舉 + 可持久化線段樹
摘要: 給長度為20000的序列。求左端點(diǎn)在[a,b]和右端點(diǎn)在[c,d]中所有的子序列，最大的中位數(shù)。
閱讀全文
posted @
2012-06-20 16:44 西月弦 閱讀(1245) |
評論 (5) 編輯
hdu 1828 線段樹求矩形周長并
摘要: 給N(N<5000)個矩形，求周長并。
閱讀全文
posted @
2012-06-04 20:54 西月弦 閱讀(466) |
評論 (0) 編輯
2012 黑龍江省賽簡要題解
摘要: 2012黑龍江省賽簡要題解(不斷更新)
閱讀全文
posted @
2012-05-30 10:33 西月弦 閱讀(334) |
評論 (0) 編輯
poj 2831 次小生成樹 or 樹鏈剖分
摘要: 給一個點(diǎn)數(shù)為N(N<1,000)的圖,Q次詢問. 每次詢問如果第i條邊的值變?yōu)関, 這條邊是否可能會在最小生成樹中.
閱讀全文
posted @
2012-05-20 15:22 西月弦 閱讀(510) |
評論 (0) 編輯
bzoj 2243 樹鏈剖分+線段樹
摘要: 在一顆點(diǎn)數(shù)為N<100,000的樹上，每個點(diǎn)有一個顏色。請你實(shí)現(xiàn)兩種操作 1. 給一段路徑u->v染色 2. 詢問路徑u->v上有多少種顏色
閱讀全文
posted @
2012-05-16 17:10 西月弦 閱讀(865) |
評論 (1) 編輯
spoj 375 樹鏈剖分+LCA+RMQ(zkw線段樹)
摘要: 在一個點(diǎn)數(shù)為N(N<10,000)的帶權(quán)樹上，支持兩個操作：1. 改變一個邊權(quán) 2. 詢問u和v之間的路徑上的最大邊權(quán)
閱讀全文
posted @
2012-05-14 22:17 西月弦 閱讀(842) |
評論 (2) 編輯
poj 3580 splay(重口味)
摘要: 給一個長度為N(N<10,000)的數(shù)列，要求支持6種操作： 1. 將區(qū)間[l,r]同時加一個數(shù) 2. 將區(qū)間[l,r]翻轉(zhuǎn) 3.將區(qū)間[l,r]旋轉(zhuǎn)若干次 4. 插入一個數(shù) 5. 刪除一個數(shù) 6.求[l,r]的最小值
閱讀全文
posted @
2012-05-12 23:48 西月弦 閱讀(619) |
評論 (0) 編輯
hdu 1890 splay + 懶惰標(biāo)記
摘要: 給一個長度為N(N<10,000)的數(shù)列，每次選取值最小的元素并翻轉(zhuǎn)前面的數(shù)列，然后刪除這個元素。請?jiān)诿看尾僮髦拜敵鲞@個最小元素的位置。
閱讀全文
posted @
2012-05-10 20:54 西月弦 閱讀(1162) |
評論 (0) 編輯
hdu 4052 線段樹+掃描線
摘要: 10^7 * 10^7 的平面上有N(N<50,000)個不相交的矩形。要在這個平面上放置一個長度為M(M<1,000)的線段，有多少種方法
閱讀全文
posted @
2012-05-09 22:20 西月弦 閱讀(537) |
評論 (0) 編輯
poj 3225 線段樹(zkw版)+ 懶惰標(biāo)記
摘要: 定義區(qū)間的交，并，差操作。假設(shè)當(dāng)前坐標(biāo)軸區(qū)間集合為S(開始為空)，給大量的詢問，格式為 命令+區(qū)間T，命令'I'代表S = S交T，'U'代表并，D和C代表S=S-T和S=T-S，S代表S=S-T并T-S。輸出最后的區(qū)間集合S。
閱讀全文
posted @
2012-05-07 20:21 西月弦 閱讀(1648) |
評論 (0) 編輯
hdu 3605 二分圖的多重匹配(匈牙利算法)
摘要: 有N(N<100,000)個人要去M(M<10)個星球，每個人只可以去一些星球，一個星球最多容納Ki個人。請問是否所有人都可以選擇自己的星球...
閱讀全文
posted @
2012-05-06 14:20 西月弦 閱讀(1546) |
評論 (0) 編輯
poj 1182 并查集
摘要: 有三個物種 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 給出N(N<50000)個生物，給出X(X<100000)個定論，請問X個定論中有多少是謊話？
閱讀全文
posted @
2012-05-06 02:28 西月弦 閱讀(403) |
評論 (7) 編輯
hdu 3603 二分+RMQ
摘要: 給一個長度不超過1,000,000的數(shù)列S。詢問Q(Q<100,000)次，在區(qū)間[l,r]里，查詢最長的元素互不相同的字串的長度。
閱讀全文
posted @
2012-05-04 22:59 西月弦 閱讀(245) |
評論 (0) 編輯
poj 1061 求模線性方程的最小整數(shù)解
摘要: 在一個長度為L的環(huán)上的有兩點(diǎn)x,y。點(diǎn)A的速度是m，點(diǎn)B的速度是n。請問二者相遇的最小整數(shù)時間。保證m,n,x,y,l都是int型正整數(shù)。
閱讀全文
posted @
2012-05-04 11:20 西月弦 閱讀(460) |
評論 (0) 編輯
poj 2528 線段樹+離散化
摘要: N(N<10000)多線段[l,r](1<=l<=r<=1,000,000,000)相互覆蓋，每個線段顏色不同，請問最后有多少種顏色?
閱讀全文
posted @
2012-05-03 19:21 西月弦 閱讀(550) |
評論 (0) 編輯
hdu 3068 Manacher算法
摘要: 求一個字符串的最長回文串。串長度小于110,000。
閱讀全文
posted @
2012-05-02 21:26 西月弦 閱讀(528) |
評論 (0) 編輯
poj 1741 樹形DP+分治+排序+容斥原理
摘要: 給你一個N(N<10000)個點(diǎn)的有權(quán)樹，請問距離不超過K(K<1,000,000,000)的點(diǎn)對有多少個?
閱讀全文
posted @
2012-05-02 16:58 西月弦 閱讀(473) |
評論 (0) 編輯
bzoj 1503 平衡樹(splay)
摘要: 用一個數(shù)據(jù)結(jié)構(gòu)來統(tǒng)計(jì)員工，有四種操作 1. 加入一個初始工資為A的員工 2. 將所有人工資提高一個數(shù) 3. 將所有人工資降低一個數(shù) 4. 詢問第K多工資的員工是誰。 其間一點(diǎn)某人的工資低于工資下限，就會立刻離開公司...
閱讀全文
posted @
2012-05-01 19:52 西月弦 閱讀(1683) |
評論 (1) 編輯
hdu 4056 線段覆蓋+并查集優(yōu)化
摘要: 在一個N*M(N<=200,M<=50000)像素的畫板上畫Q(Q<=50000)個圖形，有矩形，圓形，倒等腰三角形，菱形四種，每個圖形有九種顏色可選擇。對于一個像素，后畫的顏色會覆蓋前面的顏色，請求出最后每種顏色的像素有多少個？
閱讀全文
posted @
2012-04-30 17:38 西月弦 閱讀(496) |
評論 (0) 編輯
codeforces 11D 基于路徑的動態(tài)規(guī)劃+bitmask
摘要: 請問在點(diǎn)數(shù)為V(V<20)的無向圖中，長度不小于3的簡單回路有多少個？(保證結(jié)果可以用long long表示， 且圖中無自環(huán)或者重邊)
閱讀全文
posted @
2012-04-29 22:14 西月弦 閱讀(896) |
評論 (0) 編輯
hdu 3980 組合博弈+動態(tài)規(guī)劃+SG函數(shù)
摘要: 給一個長度為 N<1000 的環(huán)。A和B兩個人每次在這個鏈上選一段長度為 M<1000 的未染色區(qū)間進(jìn)行染色。直到某人不能進(jìn)行此操作時判此人負(fù)。假設(shè)兩人都足夠聰明，請你判斷誰會取得勝利？
閱讀全文
posted @
2012-04-28 23:14 西月弦 閱讀(447) |
評論 (0) 編輯
hdu 4200 高斯消元法 + 枚舉
摘要: N(N<100)個帶開關(guān)的燈泡排成一行，每個燈泡的開關(guān)可以轉(zhuǎn)換自己，左邊連續(xù)D個和右邊連續(xù)D個燈泡的開關(guān)狀態(tài)?，F(xiàn)在給你每個燈泡的初始狀態(tài){Ai}，請問最少開關(guān)多少次能把所有的燈熄滅？
閱讀全文
posted @
2012-04-27 18:26 西月弦 閱讀(613) |
評論 (0) 編輯
hdu 4123 樹形動態(tài)規(guī)劃+二分+單調(diào)隊(duì)列
摘要: 給出一個N個點(diǎn)的帶權(quán)樹(N <= 50000)。每個點(diǎn)到任意葉子節(jié)點(diǎn)的最長距離記為Di。詢問M < 300次，對每次詢問，找到長度最大的區(qū)間[l,r]，使得Di(l<=i<=r)的最大值和最小值的差不超過Q。
閱讀全文
posted @
2012-04-26 16:42 西月弦 閱讀(456) |
評論 (0) 編輯
zoj 3541 基于區(qū)間的動態(tài)規(guī)劃
摘要: N個按鈕在一條直線上排列，給出每個按鈕的坐標(biāo)(Xi,0)。每個按鈕按下之后在Ti秒之后馬上彈起，你一開始在最左端的按鈕上，每移動1個單位長度需要1秒鐘。
請問你能否在某一時刻使所有按鈕都是按下的。如果可以輸出任一方案。
閱讀全文
posted @
2012-04-25 12:01 西月弦 閱讀(928) |
評論 (0) 編輯
hdu 4114 動態(tài)規(guī)劃+bitmask+最短路
摘要: 給一個點(diǎn)數(shù)為N(N<50)的帶權(quán)無向圖。其中有K個景點(diǎn)，參觀每個景點(diǎn)有一個代價 Ti。有一些地方可以獲得一些景點(diǎn)的票，如果持票參觀景點(diǎn)i則代價為 FTi。 保證K<=8，F(xiàn)Ti <= Ti。 請問從景點(diǎn)1出發(fā),參觀全部的景點(diǎn)，再回到景點(diǎn)1的最小代價是多少。路的權(quán)也計(jì)算在代價中。
閱讀全文
posted @
2012-04-24 20:11 西月弦 閱讀(1818) |
評論 (0) 編輯
hdu 2829 動態(tài)規(guī)劃+斜率優(yōu)化
摘要: 給你一個序列A，請你把序列A分成連續(xù)K個子段，每個子段的代價是 sum(A[i]*A[j]) 其中 i < j。請問如何分組使代價最小。
數(shù)據(jù)范圍|A|,K <100
閱讀全文
posted @
2012-04-24 14:51 西月弦 閱讀(948) |
評論 (3) 編輯