按照老師給的題目做了四道題
食物計劃：二維背包。背包什么的最熟了，有空再復習一下單調(diào)的多重背包就完美了
產(chǎn)品排序：和養(yǎng)豬一樣是貪心+DP，現(xiàn)場時看到就戰(zhàn)略放棄，暴搜30分。
回家后仔細想了一下AC。
二叉蘋果樹：樹形DP寫爛掉了，基本上是現(xiàn)場AC，有空出一下模板。
養(yǎng)豬：困擾我好久的題目，貪心+DP，方程式早就寫出來，可今天才知道原來ans不是F[n][k]是F[n][j]中的最大值。
貪心+DP的基本上與養(yǎng)豬類似，用pair+sort實在太方便了?。╬ascal代碼有兩面紙）
養(yǎng)豬AC代碼
const int maxn=1001;
pair<int,int>x[maxn];
int n,k,ans=0;
bool cmp(pair<int,int> a,pair<int,int> b)
{return a.SD>b.SD;}
int F[maxn][maxn];
int main(){
fin>>n>>k;
FOR(i,1,n)fin>>x[i].FT;
FOR(i,1,n)fin>>x[i].SD;
sort(x+1,x+n+1,cmp);
FOR(i,1,n)FOR(j,1,min(i,k))
F[i][j]=max(F[i-1][j],F[i-1][j-1]+max(x[i].FT-x[i].SD*(j-1),0));
FOR(j,1,k)ans=max(ans,F[n][j]);//ans=F[n][k];直接ans就錯了?。。?nbsp;
fout<<ans;
fin.close();
fout.close();
return 0;
}DP的生成方式：
1.轉(zhuǎn)移法：直接把狀態(tài)方程寫上去，利用已有解推出現(xiàn)在的解。
如F[i][j]=max(min(F[i-1][j-1],j),min(F[i-1][j],n-j))
優(yōu)點：便于理解，書寫方便。
缺點：如果對于已有解的判定比較復雜，則不易書寫。
例題：
產(chǎn)品排序2.主動更新發(fā)：利用現(xiàn)有解更新后面的解。
如if(F[i][j]) F[i+A[i]][j]=max(F[i+A[i]][j],F[i][j]+B[i])
優(yōu)點：先判定該解是否合法，再更新后面的。
缺點：不易理解狀態(tài)轉(zhuǎn)移方程。
例題：
養(yǎng)豬多叉轉(zhuǎn)二叉后方程式基本不變
多叉轉(zhuǎn)二叉核心代碼
MM(last,0);//孩子的最后的兄弟，last[i]=0,表示沒有左孩子。
if(!last[b])Left[b]=a;
else Right[last[b]]=a;
last[b]=a;