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