2020-2021:teams:legal_string:jxm2001:动态规划_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:动态规划_3 [2021/01/14 20:15] jxm2001 |
2020-2021:teams:legal_string:jxm2001:动态规划_3 [2021/01/14 20:28] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 20: | 行 20: | ||
| \text{dp}(i,j)=\max(\text{dp}(i-sz_i,j),\text{dp}(i-1,j-w_i)+v_i) | \text{dp}(i,j)=\max(\text{dp}(i-sz_i,j),\text{dp}(i-1,j-w_i)+v_i) | ||
| $$ | $$ | ||
| + | |||
| + | 时间复杂度 $O(nm)$。 | ||
| <code cpp> | <code cpp> | ||
| 行 39: | 行 41: | ||
| ==== 点对优化 ==== | ==== 点对优化 ==== | ||
| - | === 例题 === | + | === 题意 === |
| + | [[https://www.luogu.com.cn/problem/P1273|洛谷p1273]] | ||
| 给定一棵以 $1$ 为根的 $n$ 阶有根树，树的每条边有费用 $f_i$，树的叶节点有价值 $v_i$。 | 给定一棵以 $1$ 为根的 $n$ 阶有根树，树的每条边有费用 $f_i$，树的叶节点有价值 $v_i$。 | ||
| 行 49: | 行 51: | ||
| 求利润非负时最多可以选取的边数。 | 求利润非负时最多可以选取的边数。 | ||
| + | === 题解 === | ||
| + | 设 $dp(i,j)$ 表示以 $i$ 为根节点的子树中选取 $j$ 个叶子结点的最大盈利，不难得出状态转移方程。 | ||
| + | |||
| + | 考虑以类似枚举 $\text{LCA}$ 的方式合并子节点结果，可以 $O(n^2)$ 完成所有状态转移。最后查询满足 $dp(1,i)\ge 0$ 的最大的 $i$ 即可。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e3+5,Inf=1e9; | ||
| + | LL dp[MAXN][MAXN]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | struct Edge{ | ||
| + | int to,w,next; | ||
| + | }edge[MAXN]; | ||
| + | void Insert(int u,int v,int w){ | ||
| + | edge[++edge_cnt]=Edge{v,w,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int sz[MAXN]; | ||
| + | void dfs(int u){ | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | dfs(v); | ||
| + | for(int j=sz[u];j>=0;j--)_rep(k,1,sz[v]) | ||
| + | dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]-edge[i].w); | ||
| + | sz[u]+=sz[v]; | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,n)_rep(j,1,n)dp[i][j]=-Inf; | ||
| + | _rep(i,1,n-m){ | ||
| + | int k=read_int(); | ||
| + | while(k--){ | ||
| + | int v=read_int(),w=read_int(); | ||
| + | Insert(i,v,w); | ||
| + | } | ||
| + | } | ||
| + | _rep(i,n-m+1,n)dp[i][1]=read_int(),sz[i]=1; | ||
| + | dfs(1); | ||
| + | for(int i=m;i>=0;i--){ | ||
| + | if(dp[1][i]>=0){ | ||
| + | cout<<i; | ||
| + | break; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/动态规划_3.1610626559.txt.gz · 最后更改: 2021/01/14 20:15 由 jxm2001
