hdu 1134 Game of Connections
摘要: Catalan Number(卡特蘭數(shù))
S(n) = C(2n,n)/(n+1)
遞推公式：a(n)=((4*n-2)/(n+1))*a(n-1)
我不理解~
閱讀全文
hdu 1133 Buy the Ticket
摘要: 考慮（m+n）個(gè)人排隊(duì)購(gòu)票的情景，第（m+n）人站在第（m+n-1）個(gè)人的后面，則第（m+n ）個(gè)人的排隊(duì)方式可以由下列兩種情況獲得：
a.第（m+n ）個(gè)人手持￥100的鈔票，則在他之前的(m+（n-1））個(gè)人中有m個(gè)人手持￥50的鈔票，有（n-1）個(gè)人手持￥100的鈔票，此種情況共有f(m,n-1);
b.第（m+n ）個(gè)人手持￥50的鈔票，則在他之前的(（m-1）+n）個(gè)人中有m-1個(gè)人手持￥50的鈔票，有n個(gè)人手持￥100的鈔票，此種情況共有f(m-1,n);
根據(jù)加法原理得到: f(m,n)=f(m-1,n)+f(m,n-1)
最終得到遞推公式：f(m,n)= C(m+n,n)-C(m+n,m+1)
即：f(m,n) = ((m+1-n) / (m+1)) *((m+n)!)
閱讀全文
vijos 1313 金明的預(yù)算方案
摘要: 背包如此之妙（有依賴的背包）
題目大意：給你一系列物品清單，其中兩物品直接可能存在主附關(guān)系，即要買(mǎi)附件必須將其附件也買(mǎi)下，比如若桌子跟椅子是主附關(guān)系，那么想買(mǎi)椅子則必須桌子也買(mǎi)下……問(wèn)題來(lái)了，給你錢(qián)N，物品若干，快快買(mǎi)吧……如何買(mǎi)？
dp[j]表示錢(qián)為j的時(shí)候買(mǎi)得東西的最大價(jià)值
一、當(dāng)物品為主件時(shí)：
1、沒(méi)有附件
MAX（不買(mǎi)，買(mǎi)主件）
2、有一個(gè)附件
MAX（不買(mǎi)，只買(mǎi)主件，買(mǎi)主件與一附件）
3、有兩個(gè)附件
MAX（不買(mǎi)，只買(mǎi)主件，買(mǎi)主件與一附件，買(mǎi)主件與兩附件）
二、當(dāng)物品為附件時(shí)：直接跳過(guò)
閱讀全文
vijos 1317 開(kāi)心的金明
摘要: 比較明顯的DP
稍稍多了一個(gè)條件，細(xì)細(xì)品味
閱讀全文
hdu 2670 Girl Love Value
摘要: 女孩的愛(ài)不易得~
先對(duì)損耗值從大到小排序，使損失最小化，然后再常規(guī)化DP
dp[i][j] = MAX(dp[i-1][j] , dp[i-1][j-1] + X)//dp[i][j] 表示前i個(gè)人中選j個(gè)的最優(yōu)值
閱讀全文
hdu 1114 Piggy-Bank
摘要: 完全背包
時(shí)間從546MS優(yōu)化到93MS，感覺(jué)不容易，呵呵~
還需要慢慢消化~
閱讀全文
hdu 2152 Fruit
摘要: 最后一道母函數(shù)
G（X,Y,Z…）=（X^i…X^j）*（Y^i…Y^j）*（Z^i…Z^j）*……
閱讀全文
hdu 2069 Coin Change
摘要: 母函數(shù)，終于貌似理解一點(diǎn)了~繼續(xù)努力吧
ans[i][j]表示i分錢(qián)用j個(gè)硬幣組合的方案數(shù)
要求記錄組合硬幣的個(gè)數(shù)~值得一看
注意點(diǎn)：1. 要求 0 cent 輸出 1
2. 如果 硬幣總數(shù)超過(guò)100,是不合法的,也就是不用計(jì)算超過(guò)100個(gè)硬幣的找錢(qián)方法.
閱讀全文
hdu 1709 The Balance
摘要: 題目大意：天平平衡問(wèn)題，給你n個(gè)砝碼，每個(gè)砝碼質(zhì)量Wi，判斷有多少種質(zhì)量不能稱量，質(zhì)量范圍是所以砝碼的質(zhì)量和
當(dāng)然啦，天平兩邊都是可以放砝碼的
閱讀全文
va家族的等級(jí)制
摘要: 先求出一段串是否為回文~
再是單調(diào)子序列思想~
閱讀全文
hdu 1171 Big Event in HDU
摘要: 母函數(shù)解決
DP算法還是想不出來(lái)
郁悶中……
閱讀全文
hdu 1085 Holding Bin-Laden Captive!
摘要: 繼續(xù)母函數(shù)
G（X）=（1+X+X^2+X^3+……）*（1+X^2+X^4+……）*（1+X^5+X^10+……）
時(shí)間不太好~
閱讀全文
hdu 1028 Ignatius and the Princess III
摘要: 再來(lái)一次母函數(shù)~
G（X）=（1+X+X^2+X^3+……）*（1+X^2+X^4+……）
閱讀全文
hdu 1398 Square Coins
摘要: 還不是很理解~
母函數(shù)G（X）=（1+X+X^2+X^3+……+X^289） *（1+X^4+X^8+X^12+……+X^288）*（1+X^9+X^18+X^27+……+X^288）*……*（1+X^289）;
閱讀全文
hdu 1728 逃離迷宮
摘要: 一次性走完一行（一列）
該題用DFS超時(shí)了，不會(huì)剪枝~5555555
閱讀全文
hdu 2512 一卡通大冒險(xiǎn)
摘要: 內(nèi)存消耗比較大~
什么類型的DP沒(méi)想清楚，dp[i][j]表示i張卡片分成j堆時(shí)的情況數(shù)，
dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1]（dp[i-1][j] * j 表示i-1張卡片分為j堆的時(shí)候，第i張卡片可以分到任意一堆中，當(dāng)然也就出現(xiàn)了一種新的分堆方法，dp[i-1][j-1]表示第i張卡片要獨(dú)立成為一堆時(shí)的方案數(shù)）
閱讀全文
hdu 2182 Frog
摘要: 青蛙吃害蟲(chóng)~
跟龜兔賽跑比較類似，第i個(gè)位置的值跟其前面位置的值有關(guān)
閱讀全文
hutc 1035 編輯距離問(wèn)題
摘要: 題目大意：串變換，有串s最少經(jīng)過(guò)多少步能夠變換成t串
先用DFS過(guò)了，（但在南開(kāi)JudgeOnline超時(shí) 555555555……）
再一次DP，總算都過(guò)了
閱讀全文
zju 1234 Chopsticks
摘要: 題目大意：從n根筷子當(dāng)中選取j對(duì)，其中一對(duì)筷子包含三根，并且要求第三跟不短語(yǔ)前兩根。要求取出的筷子長(zhǎng)度差（前兩根的長(zhǎng)度差）的平方的和最小。
num[i] 表示第i+1個(gè)筷子與第i個(gè)筷子長(zhǎng)度差的平方~
開(kāi)始從前面往后推，漏洞百出:dp[i][j]表示從1……i個(gè)筷子中選取j對(duì)，
dp[i][j] = MIN(dp[i-1][j],dp[i-3][j-1] + num[i-2]);
問(wèn)題在哪？ 第i個(gè)筷子能用，
一種情況：第i-1個(gè)筷子能與第i-2個(gè)筷子配對(duì)了（來(lái)了第三根筷子i）；
二種情況：影響1……i-1個(gè)筷子中取j對(duì)筷子的配對(duì)情況。WHY？think about~
最后從后往前推:dp[i][j]表示從i……n個(gè)筷子中選取j對(duì)，
dp[i][j] = MIN(dp[i+1][j],dp[i+2][j-1] + num[i]);
沒(méi)問(wèn)題了吧~ 第i個(gè)筷子取，則必與第i+1個(gè)筷子配對(duì)，不取則可以忽略它（就因?yàn)樗钱?dāng)前最短的）
閱讀全文
hdu 1026 Ignatius and the Princess I
摘要: BFS+保存路徑
可以試想一下從終點(diǎn)走點(diǎn)始點(diǎn)，這樣路徑是否好處理一點(diǎn)~
閱讀全文
hdu 1421 搬寢室
摘要: 搬寢室——從n個(gè)物品中選取k對(duì)，使得每對(duì)物品質(zhì)量差的平方之和最小
賦初值的時(shí)候要小心~
dp[i][j]表示從前i個(gè)物品中選取j對(duì)物品的最優(yōu)值，
dp[i][j]=MIN(dp[i-1][j],dp[i-2][j-1]+(w[i] - w[i-1])*(w[i] - w[i-1]))，
取第i個(gè)物品，則必取第i-1個(gè)物品，WHY？相連物品平方差必定最小~
在WXH幫助下完成，學(xué)習(xí)學(xué)習(xí)~
閱讀全文
并查集的初級(jí)應(yīng)用及進(jìn)階
摘要: 并查集資料
拷貝牛人http://blog.csdn.net/pure_life/archive/2008/09/13/2922118.aspx
閱讀全文
hdu 1558 Segment set
摘要: 題目大意：求交叉在一起的線段的條數(shù)，如果線段A連接著另外兩條不相交線段B、C，則認(rèn)為B、C也是相交的
簡(jiǎn)而言之就是輸出要查找的線段所在集合中線段數(shù)為多少~
主要參考了牛人的代碼，尋求了很久才找到一個(gè)能正確判斷兩線段是否相交的函數(shù)，珍惜珍惜~
并查集中的路徑壓縮，就這么回事~
閱讀全文
hdu 1272 小希的迷宮
摘要: 小希的迷宮~
題意：要求無(wú)回路，同屬于一個(gè)集合
注意 輸入數(shù)據(jù) 0 0 的情況，應(yīng)該輸出 Yes~
并查集判連通，未輸入的結(jié)點(diǎn)不用考慮，用visited數(shù)組標(biāo)志結(jié)點(diǎn)是否出現(xiàn)過(guò)
矮樹(shù)并入高樹(shù) 有益于 查找
閱讀全文
hdu 1232 暢通工程
摘要: 并查集好不簡(jiǎn)單，哎~笨牛~
不過(guò)在學(xué)弟的耐心指導(dǎo)下還是解決了，也算是跨進(jìn)了并查集的門(mén)檻吧……
核心問(wèn)題：求出有多少個(gè)集合~
閱讀全文
hdu 2141 Can you find it?
摘要: 該題很容易超時(shí)，提交20余次~ 很郁悶~
先列舉序列a與序列b的和，然后再進(jìn)行二分查找
for(i=0 ; i< lena; i++)
for(j=0 ; j< lenb; j++)
temp[k++] = a[i] + b[j];
閱讀全文
hdu 1239 Calling Extraterrestrial Intelligence Again
摘要: 典型的搜索
題目大意：給出三個(gè)整數(shù)m a b 其中 4 < m <= 100000 ， 1 <= a <= b <= 1000，尋找一對(duì)素?cái)?shù)p q 使得
p*q<=m && a/b <= p/q <=1 ,要求使p*q盡可能大
按常規(guī)思想，數(shù)據(jù)量大肯定超時(shí)~
如果q為某個(gè)大于10000的素?cái)?shù)，那么當(dāng)p<10時(shí)，p/q < 0.001(然而a/b>=0.01),當(dāng)p>10時(shí),p*q>100000(然而m<=100000)
因此 p q 都是在10000以內(nèi)的素?cái)?shù)~
剪枝：if ( a[j]>m || a[j]*a[i]>m || ( (double)a[i]/a[j])
more~ 閱讀全文
hdu 1010 Tempter of the Bone
摘要: 走迷宮-主要考查奇偶剪枝法
題目大意：給出起始位置，然后給定時(shí)間T，在時(shí)間T內(nèi)從出發(fā)點(diǎn)走到終點(diǎn)，每步只能往上、下、左、右四個(gè)方向走一步，時(shí)間是1，不能在原地停留。如果到達(dá)某點(diǎn)的剩余時(shí)間為奇數(shù)，那么必定是在奇數(shù)步內(nèi)走到終點(diǎn)，也就是兩點(diǎn)的 行差絕對(duì)值 + 列差絕對(duì)值 也要是奇數(shù)~ 奇偶剪枝
閱讀全文
hdu 1072 Nightmare
摘要: 做噩夢(mèng)了~
逃了好久好久~
在炸彈爆炸之前逃出迷宮，定時(shí)炸彈時(shí)間可以重置~
mark[i][j]表示第i行j列位置時(shí)剩余爆炸時(shí)間，當(dāng)然是時(shí)間越長(zhǎng)越好
閱讀全文
hdu 1298 T9
摘要: 字典樹(shù)+dfs+剪枝
先理解題意，給你一連串?dāng)?shù)字，輸出其對(duì)應(yīng)的出現(xiàn)頻率最大的單詞
在每一步深搜之前先做剪枝~
閱讀全文
hdu 1075 What Are You Talking About
摘要: Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 1238 Accepted Submission(s): 340
先用map勉強(qiáng)過(guò)了（1593MS 37528K）~
然后再建字典樹(shù)（296MS 59804K）~
閱讀全文
hdu 1800 Flying to the Mars
摘要: 利用字典樹(shù)統(tǒng)計(jì)數(shù)字出現(xiàn)次數(shù)，輸出出現(xiàn)次數(shù)最多的一次。
注意因?yàn)槭谴髷?shù)，故需考慮除去前綴0，因0010 、010是同一個(gè)數(shù)字
字典樹(shù)：又稱為T(mén)rie，是一種用于快速檢索的多叉樹(shù)結(jié)構(gòu)。Trie把要查找的關(guān)鍵詞看作一個(gè)字符序列，并根據(jù)構(gòu)成關(guān)鍵詞字符的先后順序構(gòu)造用于檢索的樹(shù)結(jié)構(gòu)；一棵m度的Trie樹(shù)或者為空，或者由m棵m度的Trie樹(shù)構(gòu)成。
特別地：和二叉查找樹(shù)不同，在Trie樹(shù)中，每個(gè)結(jié)點(diǎn)上并非存儲(chǔ)一個(gè)元素。
閱讀全文
hdu 1195 Open the Lock
摘要: 對(duì)每個(gè)數(shù)字只要三種轉(zhuǎn)換狀態(tài)：加1，減1，跟其后面一個(gè)數(shù)字交換位置。
需注意的是最后一個(gè)數(shù)字沒(méi)有交換，數(shù)字9加1變?yōu)?，數(shù)字1減1變?yōu)?。
很傳統(tǒng)的一個(gè)BFS……
利用hash表標(biāo)志走過(guò)的狀態(tài)……
閱讀全文
hdu 1013 Digital Roots
摘要: 開(kāi)始用int,WA,接著用__int64,還是WA,最后改用字符數(shù)組,新的錯(cuò)誤：Compilation Error, WHY?
C語(yǔ)言要求變量的定義應(yīng)該放在所有的執(zhí)行語(yǔ)句之前，而C++則放松了限制，只要求在第一次使用該變量之前進(jìn)行定義即可……
切記切記……
看下面代碼————煥然大悟！！！
閱讀全文
hdu 1142 A Walk Through the Forest
摘要: 記憶法搜索
因?yàn)?是出發(fā)點(diǎn)，2是終點(diǎn)，先運(yùn)用dijkstra（迪杰斯特拉）算法計(jì)算出所有點(diǎn)到終點(diǎn)的最短路徑。
然后記憶法搜索，從1開(kāi)始，與1相連且到終點(diǎn)2的距離比dist[1]小的點(diǎn)都可行，依此類推……
閱讀全文
zju 1076 Gene Assembly
摘要: 簡(jiǎn)單貪心
類似活動(dòng)安排問(wèn)題
閱讀全文
hdu 1078 FatMouse and Cheese
摘要: 米老鼠覓食
從坐標(biāo)0、0出發(fā)，依次找其周圍最優(yōu)的方案然后遞歸下去，同時(shí)記錄搜索過(guò)的地方
閱讀全文
zju 2022 Factorial
摘要: 計(jì)算N！后面零的個(gè)數(shù)
閱讀全文
zju 1199 Point of Intersection
摘要: 公式推導(dǎo)過(guò)程
temp=(y1-y2)/(x1-x2);
sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))/sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))=r1/r2;
(y1-y0)/(x1-x0)=temp;
(y2-y0)/(x2-x0)=temp;
閱讀全文
zju 1047 Image Perimeters
摘要: 求X塊圖的面積
從出發(fā)點(diǎn)向四周擴(kuò)散，如果X的一邊為.或者是邊界，則sum++
閱讀全文
zju 3049 Diablo II Items
摘要: 題目的背景是鼎鼎大名的暗黑2，這題講的是關(guān)于暗黑賣物品的一個(gè)問(wèn)題。暗黑里面有兩種物品，普通物品和魔法
物品。普通物品只有一個(gè)普通出售價(jià)格，而魔法物品有兩個(gè)出售價(jià)格，鑒定前的價(jià)格和鑒定后的價(jià)格，用鑒定卷軸
鑒定魔法物品，物品的價(jià)格就變成鑒定后價(jià)格了。然后現(xiàn)在沒(méi)有錢(qián)，有一堆物品要賣，其中有若干的普通物品和若
干的魔法物品，其中魔法物品都是沒(méi)有鑒定過(guò)的。同時(shí)，可以買(mǎi)無(wú)限量的鑒定卷軸（價(jià)格cost）。現(xiàn)在的問(wèn)題是怎么
賣東西才能讓最后的總收益最大。這題主要考察的是分析題目的能力。首先發(fā)現(xiàn)，所有的普通物品可以直接賣掉，
因?yàn)樗麄冎挥幸粋€(gè)價(jià)格。然后考察魔法物品（鑒定前價(jià)格normalPrice，鑒定后價(jià)格magicPrice），如果
normalPrice >= magicPrice - cost，那么也可以把它們當(dāng)作普通物品一樣直接賣了，因?yàn)殍b定它們完全不會(huì)有任
何的收獲。然后，剩下的物品，鑒定后賣總是比不鑒定直接賣要賺錢(qián)的。我們可以發(fā)現(xiàn)，一旦我們有錢(qián)可以買(mǎi)得起
一個(gè)鑒定卷軸，買(mǎi)一個(gè)來(lái)鑒定一個(gè)魔法物品然后賣掉后，錢(qián)會(huì)增加，于是可以繼
閱讀全文