首页 > 其他分享 >P8564 ρars/ey 题解

P8564 ρars/ey 题解

时间:2024-09-26 18:14:26浏览次数:8  
标签:P8564 ars int 题解 ++ edge siz now dp

显然树上背包。

首先一眼会想到的状态:\(dp_{i,j}\) 表示 \(i\) 的子树最后剩下 \(j\) 个结点的最小代价。

然而开始写会发现这并不好 DP。

于是我们换一个想法:\(dp_{i,j}\) 表示 \(i\) 的子树删去 \(j\) 个结点的最小代价。

则有转移方程:

\[dp_{i,j} = \min_{v \in son(i)}\{dp_{i, j - k} + dp_{v,k}\} \]

但是注意到这个方程 \(j\) 最多到 \(siz_{i} - 1 - cntson_{i}\)(\(cntson_{i}\) 表示 \(i\) 的儿子的数量),我们还需要一个方程:

\[dp_{i,siz_{i} - 1} = \min\{dp_{i,j} + f_{siz_{i} - j}\} \]

于是这样就完美了,\(O(n^2)\) 足够通过此题

代码如下:

#include<bits/stdc++.h>
#define MAXN 5010
#define INF 0x7f7f7f7f7f7f7f7f
using namespace std;
typedef long long ll;
struct edge{ int pre, to; };
edge e[MAXN << 1];
int n, cnt;
int head[MAXN], f[MAXN];
namespace strange{
    ll dp[MAXN][MAXN], siz[MAXN];
    void dfs(int now, int fa){
        dp[now][0] = 0; siz[now] = 1;
        for(int i = head[now]; i; i = e[i].pre){
            if(e[i].to == fa) continue;
            dfs(e[i].to, now);
            for(int j = siz[now] + siz[e[i].to] - 1; j > 0; j--){
                for(int k = max(j - siz[now], 1ll); k <= siz[e[i].to] - 1 && k <= j; k++){
                    if(dp[e[i].to][k] >= INF || dp[now][j - k] >= INF) continue;
                    dp[now][j] = min(dp[now][j], dp[e[i].to][k] + dp[now][j - k]);
                }
            }
            siz[now] += siz[e[i].to];//记得先 DP 后加 siz,否则复杂度是假的,这个蒟蒻就是因为这个少了 30 分
        }
        for(int j = 0; j < siz[now] - 1; j++){
            dp[now][siz[now] - 1] = min(dp[now][siz[now] - 1], dp[now][j] + f[siz[now] - j]);
        }
    }
    void main(){
        memset(dp, 0x7f, sizeof(dp));
        dfs(1, 0);
        printf("%lld\n",dp[1][siz[1] - 1]);
    }
}
void add_edge(int u, int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
int main(){
    // freopen("T2ex2.in", "r", stdin);
    scanf("%d",&n);
    for(int i = 1; i < n; i++) scanf("%d",&f[i + 1]);
    for(int i = 1; i < n; i++){
        int u, v; scanf("%d%d",&u,&v);
        add_edge(u, v); add_edge(v, u);
    }
    strange::main();
    return 0;
}

标签:P8564,ars,int,题解,++,edge,siz,now,dp
From: https://www.cnblogs.com/NightTide/p/18434019

相关文章

  • 题解:UVA1456 Cellular Network
    UVA1456CellularNetwork题解夭寿了!30行写完紫题了!更新:已联系管理员修改难度,现在是绿题题意很简单,不再赘述。首先一个小贪心,将概率\(u​\)进行从大到小的排序,优先查看概率大的区域,显然这样能够保证访问数量期望最小。接着考虑如何将区域分组。一个显而易见的思路是动态......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......
  • 题解:P4288 [SHOI2014] 信号增幅仪
    很好一题目,使我的最小圆覆盖旋转。先假设\(p=1\)。这是最简单的情况。这个时候我们就得到了一个裸的最小圆覆盖。当\(p\not=1\),但是\(a=0\)的时候。圆就变成了对称轴与坐标轴平行的椭圆,运用高中知识仿射一下,又回到了最小圆覆盖。在一般的情况下,我们先通过坐标的旋转......
  • 《超级机器人大战30》缺少roboex32.dll启动遇阻怎么办?轻松应对《超级机器人大战30》ro
    当《超级机器人大战30》因缺少roboex32.dll文件而启动遇阻时,可以尝试以下几种解决方案来轻松应对这一问题:一、下载并替换缺失的DLL文件寻找可靠来源:首先,需要在互联网上找到可靠的roboex32.dll文件下载源。建议访问官方网站、微软官方下载中心或知名的软件下载站点,以确保下载......
  • AT_arc176_e [ARC176E] Max Vector 题解
    发现数据范围很小,考虑最小割。先对题面做一个转化:构造两个序列\(X=(X_1,X_2,\dots,X_N),Y=(Y_1,Y_2,\dots,Y_N)\)最小化\(\sumX_i+Y_i\),有\(M\)个限制,每个限制有一个序列\(A_1,A_2,\dots,A_n\),需要满足\(\foralli,X_i\geA_i\)或者\(\foralli,Y_i\geA_i\)。考虑怎......
  • JsonParser.Feature各枚举项的作用
    枚举项作用ALLOW_BACKSLASH_ESCAPING_ANY_CHARACTER允许反斜杠转义任何字符。ALLOW_COMMENTS允许在JSON内容中包含注释。ALLOW_MISSING_VALUES允许在JSON数组中缺少值。ALLOW_NON_NUMERIC_NUMBERS允许非数字的数值(如NaN、Infinity)。ALLOW_NUMERIC_LEADING_Z......
  • 1. 两数之和题解
    题目描述[!NOTE]总结:找出整数数组中两数之后等于目标值的两个数,然后返回其下标给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素......
  • 「FJWC2020Day5-zzq」rng 题解
    题意简述一个长度为\(n\)的实数序列\(a_i\),其中\(a_i\)为\([l_i,r_i]\)中独立均匀随机选取的实数。你只能通过交换相邻两个数,使得\(a_i\)单调不降。你需要求出你最少操作次数的期望,对\(M=998244353\)取模。\(1\leqn\leq10^6\),\(0\leql_i\ltr_i\leq10^{1......
  • 使用豆包MarsCode 实现高可用扫描工具
    以下是「 豆包MarsCode 体验官」优秀文章,作者郝同学测开笔记。前言最近接触K8s,了解到K8s提供了非常方便的实现高可用的能力,再加上掘金推出「豆包MarsCode初体验」征文活动,所以打算使用豆包MarsCodeIDE来实现一个高可用扫描工具。豆包MarsCodeIDE是一个云端AIIDE平台。通......
  • 留学期间学业常见问题解决办法,包括不能毕业的状况
    留学期间学业常见问题解决办法,包括不能毕业的状况【国外留学期间,遇到考试挂科的情况,影响了毕业,该怎么办?】考试挂科是一个很常见的现象,而国外院校,因为每个学校的规定不同,有的学校学生有补考机会,但是有的学校如果学生考试挂科情况很严重,或许就没有补考的机会了。这都没关系,重要的是,你......