NOI导刊树型动态规划.pptVIP

树型动态规划;加分二叉树;样例 中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145.;分析;动态规划;选课;分析;样例分析;转化为二叉树;动态规划;样例求解过程：初始f(i,0)=0 f(6,1)=6, f(5,1)=max{1,6}=6, f(7,1)=2 f(4,1)=max{1,2}=2, f(1,1)=max{1,f(4,1)}=2 f(3,1)=4, f(2,1)=max{1,4}=4 f(5,2)=7 f(7,2)=max{f(5,1)+2}=8 f(4,2)=max{f(7,2),f(7,1)+1}=8 f(1,2)=max{f(4,2),f(4,1)+2}=8 f(2,2)=max{f(1,1)+1, f(3,1)+1)}=5 f(7,3)=9 f(4,3)=max{f(7,2)+1,f(7,3)}=9 f(1,3)=max{f(4,2)+1,f(4,3)}=9 f(2,3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9 f(2,4)=max{f(1,3)+1, f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13 ;//读入数据 ,转化为孩子兄弟表示 fin n m; score[n+1] = 0; brother[n+1] = 0; // 输入数据并转化为左儿子右兄弟表示法 for (int i=1; i=n; ++i) { int a, b; fin a b; if (a == 0) a = n + 1; score[i] = b; brother[i] = child[a]; child[a] = i; };void dfs( int i, int j) { if (visited[i][j]) return; visited[i][j] = 1; if (i==0 || j==0) return; dfs(brother[i], j); // 如果不选i，则转移到状态(brother[i], j) f[i][j] = f[brother[i]][j]; for (int k=0; kj; ++k) { // 选择i，枚举学习多少以i为根的 (j-k-1)，并转移到相应状态 dfs(brother[i], k); dfs(child[i], j-k-1); // 更新答案 if (f[brother[i]][k] + f[child[i]][j-k-1] + score[i] f[i][j]) f[i][j] = f[brother[i]][k] + f[child[i]][j-k-1] + score[i]; } };软件安装（2010河南省选）;分析;分析;树型动态规划;警卫安排;分析样例 该图有6个区域如图1，安排情况如图2，红色点为安排了警卫。 2号警卫可以观察1，2，5，6；3号警卫可以观察1，3； 4号警卫可以观察1，4； 费用：16+5+4=25 ;分析;动态规划;procedure work(now:longint); var i,j,sum,tmp:longint; begin for i:=1 to t[now] do work(w[now,i]);　 //对每个儿子进行处理 f[now,0]:=0; //以下处理now被父亲看到 for i:=1 to t[now] do inc(f[now,0],f[w[now,i],1]); //now的儿子被儿子看到 　sum:=0;　　//以下处理在now被儿子看到的 for i:=1 to t[now] do // now的儿子被儿子看到或者或安排警卫； inc(sum, min(f[w[now,i],1],f[w[now,i],2])); f[now,1]:=maxlongint;　 for i:=1 to t[now] do　 //枚举哪个儿子放警卫 begin tmp:=sum-min(f[w[now,i],1],f[w[now,i],2])+f[w[now,i],2]; f[now,1]:=min(f[now,1],tmp); end; f[no