P1216 [IOI1994][USACO1.5]數(shù)字三角形 Number Triangles
- 第一次tle了，然后發(fā)現(xiàn)自己犯了一個(gè)很傻的錯(cuò)誤，想用數(shù)組遞歸，可每次還是重算了，于是有加了一些，就AC了
記錄詳情 - 入手點(diǎn)：發(fā)現(xiàn)題目問(wèn)的是最值，于是想到貪心和dp（若暴力搜索的，感覺(jué)基礎(chǔ)算法是O（n?。杏X(jué)沒(méi)有直接貪心的思路，且dp好像比較好寫(xiě)（數(shù)據(jù)不是特別大），于是使用dp
P1115 最大子段和
- 錯(cuò)了一個(gè)點(diǎn)，感覺(jué)是因?yàn)橐曳强兆佣危ㄈ羲袛?shù)全是負(fù)數(shù)，則輸出應(yīng)該 < 0，而我的解法的輸出是0），可沒(méi)想好如何用動(dòng)態(tài)規(guī)劃解決
記錄詳情
最長(zhǎng)上升子序列
- O(n^2)用dp很好寫(xiě)可過(guò)不了，優(yōu)化要用dirworth定理證明（或找規(guī)律），不會(huì)
dp博客（找到后刪掉此條）
P1464 Function
- 直接記憶化搜索即可
- 記錄詳情
P1255 數(shù)樓梯
- 用數(shù)組遞歸（因?yàn)楸容^稠密），n <= 5000 ，必須用高精度
- 開(kāi)始時(shí)用struct時(shí)沒(méi)寫(xiě)構(gòu)造函數(shù)，于是沒(méi)過(guò)，可記得有老師說(shuō)不寫(xiě)構(gòu)造函數(shù)會(huì)自動(dòng)清空
- 記錄詳情
-
總結(jié)（待補(bǔ)充）
P1002 過(guò)河卒
- dp計(jì)數(shù)，若被馬踩，直接return0，若超出棋盤(pán)，return0，若到達(dá)，return1，否則dp
- long long
- 記錄詳情
P1049 裝箱問(wèn)題
- 這道題老師講轉(zhuǎn)移方程是dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w[i]] （可用滾動(dòng)數(shù)組省略i）可感覺(jué)只能解決是否能完美放下的問(wèn)題
P1541 烏龜棋
- 這道題直接用dp（a，b，c，d）表示有a個(gè)1，b個(gè)2，c個(gè)3，d個(gè)4，直接dp即
- 老師又說(shuō)可以用map做記憶化，沒(méi)想明白
P1048 采藥
- 這道題感覺(jué)直接dp即可，樣例和手動(dòng)生成的都過(guò)了，可最后只ac了2個(gè)點(diǎn)
- 記錄詳情
P1164 小A點(diǎn)菜
P1507 NASA的食物計(jì)劃
這題第一次樣例過(guò)了，但是提交只得了10分，檢查后發(fā)現(xiàn)有個(gè)錯(cuò)誤；想問(wèn)一下老師，如何自己出測(cè)試數(shù)據(jù)
yl教練繼續(xù)：
P1060 開(kāi)心的金明
01背包
P1064 金明的預(yù)算方案
變種01背包
image.png
image.png
image.png
SP39 PIGBANK - Piggy-Bank
完全背包
image.png
image.png
image.png
image.png
image.png
自學(xué)【多重背包】和【混合背包】
image.png
P1466 集合 Subset Sums
01背包計(jì)數(shù)
P1474 貨幣系統(tǒng) Money Systems
完全背包計(jì)數(shù)
P2733 家的范圍
矩形DP
image.png
image.png
P1006 傳紙條
矩形DP
image.png
P1387 最大正方形
矩形DP
image.png
