游戏公司招聘网站,高端h5网站建设 上海,传奇游戏开发,ui设计师需要考什么证书因为上次比赛sb地把一道树形dp当费用流做了#xff0c;受了点刺激#xff0c;用一天时间稍微搞一下树形DP#xff0c;今后再好好搞一下#xff09; 基于背包原理的树形DP poj 1947 Rebuilding Roads 题意#xff1a;给你一棵树,让你求最少剪掉多少条边可以剪出一棵点数为m… 因为上次比赛sb地把一道树形dp当费用流做了受了点刺激用一天时间稍微搞一下树形DP今后再好好搞一下 基于背包原理的树形DP poj 1947 Rebuilding Roads 题意给你一棵树,让你求最少剪掉多少条边可以剪出一棵点数为m的子树. 解法dp[i][j]表示i节点得到j个节点的子树至少要剪多少边对于每个节点a和它的孩子b如果剪掉b则dp(s)[a][j]dp(s-1)[a][j], 如果保留a,bdp(s)[a][j]min{dp(s-1)[a][j - k] dp[b][k]}.初始条件为dp[a][1] 0; 为了不产生后效性需要由大到小枚举j的值。ansmin{dp[i][m] 1dp[root][m]} [java] view plaincopy print? void dfs(int a) { dp[a][1] 0; for (int i E[a]; i ! -1; i buf[i].ne) { int b buf[i].be; dfs(b); num[a]num[b]; for (int j Math.min(m,num[a]); j 0; j--) { dp[a][j]; for (int k 1; k jknum[b]; k) dp[a][j] Math.min(dp[a][j], dp[a][j - k] dp[b][k]); } } } void dfs(int a) {dp[a][1] 0;for (int i E[a]; i ! -1; i buf[i].ne) {int b buf[i].be;dfs(b);num[a]num[b];for (int j Math.min(m,num[a]); j 0; j--) {dp[a][j];for (int k 1; k jknum[b]; k)dp[a][j] Math.min(dp[a][j], dp[a][j - k] dp[b][k]);}}} poj 1155 TELE 题意其余点为转发站。客户端i愿支付的钱为pay[i],每条边需要的花费固定问电台在保证不亏损的情况下解法:dp[a][j] Math.max(dp[a][j], dp[a][j - k] dp[b][k]- buf[i].v);节点a给j个节点输送信号能赚多少钱 j k num有N座城堡每座城堡都有一定的宝物允许攻克M个城堡并获得里面的宝物。但有些城堡必须先攻克其他某一个特定的城堡才能攻克问攻克M个城堡所获得的最多宝物的数量。 dp[a][j] Math.max(dp[a][j], dp[a][k] dp[b][j - k]);dp[a][j]代表从i开始攻克j的城堡的最大获利初始化时dp[i][1]i城堡内的宝贝数dp[0][1]0;dp[i][0]0;ansMax{dp[i][m],dp[0][m1]}; ------------------------------------------------------------------------------------------------------ Poj 2486 Apple Tree 题意:苹果树上有n个节点每个节点数上有若干个苹果问最多走m步后至多能吃多少个苹果。 解法每个在路径上的节点有两种形态一是以此节点为起点到达某点后不再返回而是从此节点出发后返回再从其它孩子继续走。因此定义dp[a][j][0]为a节点第一种情况下走j步的最大获利dp[a][j][1]为a节点在第二种情况下走j步的最大获利。转移方程为 dp[a][j][0]Math.max(dp[a][j][0],dp[a][k][1]dp[b][j-k-1][0]); dp[a][j][0]Math.max(dp[a][j][0],dp[a][k][0]dp[b][j-k-2][1]); dp[a][j][1]Math.max(dp[a][j][1],dp[a][k][1]dp[b][j-k-2][1]) 初始化dp[i][0][1]dp[i][0][0]i节点的苹果数。ansMax{0dp[1][i][0]}; Poj 1655 balancing Act/poj 3107 Godfather 题意一个节点的平衡因子定义为删到此节点后形成的节点数最多的子树。求一棵树中平衡因子最大的节点。 解法定义num[i]为i节点为根的子树的节点数max[i]为i节点孩子节点数的最大值一个节点的平衡因子ans Math.max(ans, first second); Sgu149HDU2196 Computer 解法一个点的最远路径或者是向下一直走或者是先走到父节点然后再从父节点开始走一条较长的路径。 对于第一种情况由底向上更新求出每点的最长路径和次长路径即可对于第二种情况如果当前节点是父节点最长路径上的点那么向上的最长路径边权父节点的次长路径否则最长路径边权父节点的最长路径。得到向上的最长路径后更新最长路径和次长路径如果更新了最长路径需要更新一下原来向下最大孩子的状态使它不是父节点最长路径上的点从上向下dfs更新一下即可。 [java] view plaincopy print? int dfs(int a) { int temp, f 0; for (int i E[a]; i ! -1; i buf[i].ne) { int b buf[i].be; temp dfs(b) buf[i].v; if (temp first[a]) { second[a] first[a]; first[a] temp; f b; } else if(tempsecond[a]) second[a]temp; } fid[a] f; isf[f] true; return first[a]; } void work(int p, int a, int v) { int temp -1; if (isf[a]) temp second[p] v; else temp first[p] v; if (temp first[a]) { second[a] first[a]; first[a] temp; isf[fid[a]] false; } else if (temp second[a]) second[a] temp; for (int i E[a]; i ! -1; i buf[i].ne) { int b buf[i].be; work(a, b, buf[i].v); } } int dfs(int a) {int temp, f 0;for (int i E[a]; i ! -1; i buf[i].ne) {int b buf[i].be;temp dfs(b) buf[i].v;if (temp first[a]) {second[a] first[a];first[a] temp;f b;}else if(tempsecond[a])second[a]temp;}fid[a] f;isf[f] true;return first[a];}void work(int p, int a, int v) {int temp -1;if (isf[a])temp second[p] v;elsetemp first[p] v;if (temp first[a]) {second[a] first[a];first[a] temp;isf[fid[a]] false;} else if (temp second[a])second[a] temp;for (int i E[a]; i ! -1; i buf[i].ne) {int b buf[i].be;work(a, b, buf[i].v);}}转载于:https://www.cnblogs.com/avcs/p/6909961.html
