zju 2852 Deck of Cards
摘要: 注意點：每張card放下時優先考慮是否能恰好組成21點，再做下一步
dp問題都是從最優子結構出發，拓展思維
閱讀全文
vijos 1313 金明的預算方案
摘要: 背包如此之妙（有依賴的背包）
題目大意：給你一系列物品清單，其中兩物品直接可能存在主附關系，即要買附件必須將其附件也買下，比如若桌子跟椅子是主附關系，那么想買椅子則必須桌子也買下……問題來了，給你錢N，物品若干，快快買吧……如何買？
dp[j]表示錢為j的時候買得東西的最大價值
一、當物品為主件時：
1、沒有附件
MAX（不買，買主件）
2、有一個附件
MAX（不買，只買主件，買主件與一附件）
3、有兩個附件
MAX（不買，只買主件，買主件與一附件，買主件與兩附件）
二、當物品為附件時：直接跳過
閱讀全文
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 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 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幫助下完成，學習學習~
閱讀全文
hdu 1078 FatMouse and Cheese
摘要: 米老鼠覓食
從坐標0、0出發，依次找其周圍最優的方案然后遞歸下去，同時記錄搜索過的地方
閱讀全文
zju 3049 Diablo II Items
摘要: 題目的背景是鼎鼎大名的暗黑2，這題講的是關于暗黑賣物品的一個問題。暗黑里面有兩種物品，普通物品和魔法
物品。普通物品只有一個普通出售價格，而魔法物品有兩個出售價格，鑒定前的價格和鑒定后的價格，用鑒定卷軸
鑒定魔法物品，物品的價格就變成鑒定后價格了。然后現在沒有錢，有一堆物品要賣，其中有若干的普通物品和若
干的魔法物品，其中魔法物品都是沒有鑒定過的。同時，可以買無限量的鑒定卷軸（價格cost）。現在的問題是怎么
賣東西才能讓最后的總收益最大。這題主要考察的是分析題目的能力。首先發現，所有的普通物品可以直接賣掉，
因為他們只有一個價格。然后考察魔法物品（鑒定前價格normalPrice，鑒定后價格magicPrice），如果
normalPrice >= magicPrice - cost，那么也可以把它們當作普通物品一樣直接賣了，因為鑒定它們完全不會有任
何的收獲。然后，剩下的物品，鑒定后賣總是比不鑒定直接賣要賺錢的。我們可以發現，一旦我們有錢可以買得起
一個鑒定卷軸，買一個來鑒定一個魔法物品然后賣掉后，錢會增加，于是可以繼
閱讀全文