按照老师给的题目做了四道题
食物计划:二维背包。背包什么的最熟了,有空再复习一下单调的多重背包就完美了
产品排序:和养猪一样是贪心+DP,现场时看到就战略放弃,暴搜30分。
回家后仔细想了一下AC。
二叉苹果树:树形DP写烂掉了,基本上是现场AC,有空出一下模板。
养猪:困扰我好久的题目,贪心+DP,方程式早就写出来,可今天才知道原来ans不是F[n][k]是F[n][j]中的最大值。
贪心+DP的基本上与养猪类似,用pair+sort实在太方便了!(pascal代码有两面纸)
![](/Images/OutliningIndicators/ContractedBlock.gif)
养猪AC代码
const int maxn=1001;
pair<int,int>x[maxn];
int n,k,ans=0;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool cmp(pair<int,int> a,pair<int,int> b)
{return a.SD>b.SD;}
int F[maxn][maxn];
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
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就错了!!!
fout<<ans;
fin.close();
fout.close();
return 0;
}DP的生成方式:
1.转移法:直接把状态方程写上去,利用已有解推出现在的解。
如F[i][j]=max(min(F[i-1][j-1],j),min(F[i-1][j],n-j))
优点:便于理解,书写方便。
缺点:如果对于已有解的判定比较复杂,则不易书写。
例题:
产品排序2.主动更新发:利用现有解更新后面的解。
如if(F[i][j]) F[i+A[i]][j]=max(F[i+A[i]][j],F[i][j]+B[i])
优点:先判定该解是否合法,再更新后面的。
缺点:不易理解状态转移方程。
例题:
养猪多叉转二叉后方程式基本不变
多叉转二叉核心代码
MM(last,0);//孩子的最后的兄弟,last[i]=0,表示没有左孩子。
if(!last[b])Left[b]=a;
else Right[last[b]]=a;
last[b]=a;