自动搬运

查看原文

来自洛谷，原作者为

	anonymous_person **

搬运于2025-08-24 22:27:36，当前版本为作者最后更新于2022-04-07 18:46:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

须知

本题解骨架是本人由官方题解翻译得来的，并补充了一些不详细的地方，修改了一些错误，自己写了每一个子任务的代码（因为官方题解代码和文本不太匹配）。

基本信息

任务名：Džumbus

提供者：Vedran Kurdija

前置技能：树论、动态规划、复杂度分析

Subtask 1

“这 $M$ 组朋友不可能将 $A$ 分享给别人的答案重新分享给 $A$。”

由这句话，我们可以知道本题中的图是无环的。

结合第一和第二个子任务中，每位朋友最多只与两位其他朋友分享答案这一特殊规定，我们可以得到，在第一和第二个子任务中，成对的朋友形成了一条链。

在这种情况下，我们可以使用一个线性的动态规划来解决第一个子任务。

首先，我们可以创建一个数组 $L[N]$，其中 $L[i]$ 表示链上第 $i$个数的真实编号。

然后，使用一种类似背包问题的方式。设置数组 $dp[P][K][B]$，表示在链中第 $P$ 个位置，我们已经饮用的džumbus的数量为 $K$，以及一个二进制标志 $B$， $B$为 $0$ 时表示处于位置$P$的人并未喝过džumbus， $B$ 为 $1$ 时表示处于位置 $P$ 的人已经喝到了足够džumbus并和别人交换过题解了。

$dp[P][K][B]$的值反映了，在这一状态下，能够交换题解的最多人数。

分析后得到的转移方程如下：

$$dp[P][K][0]=\max\{dp[P-1][K][0],dp[P-1][K][1]\}\\dp[P][K][1]=\max\{dp[P-1][K-D_{L[P]}-D_{L[P-1]}][0]+2,dp[P-1][K-D_{L[P]}][1]+1\} $$

可以通过滚动数组删去第一维。

查询$S_{i}$的答案等于 $\max \{ dp[N][S_{i}][0],dp[N][S_{i}][1] \}$。

这个方法的总时间复杂度为 $O(N\cdot \max\limits_{i=1}^{q}\{S_{i}\} )$。

#include<bits/stdc++.h>
using namespace std;
const int NUM=1005;
const int INF=0x3f3f3f3f;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
	{
        if(c=='-')
		{
            f=-1;
        }
		c=getchar();
	}
    while(c>='0'&&c<='9')
	{
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
	}
    return x*f;
}
int n,m,d[NUM],num,head[NUM],ind[NUM],cnt,l[NUM],q,s,dp[NUM][2];
struct edge
{
    int next;
    int to;
}e[NUM*2];
void add_edge(int from,int to)
{
    num++;
    e[num].next=head[from];
    e[num].to=to;
    head[from]=num;
    ind[to]++;
}
void dfs(int u,int fa)
{
    int v;
    l[++cnt]=u;
    for(int i=head[u];i;i=e[i].next)
    {
        v=e[i].to;
        if(v!=fa)
        {
            dfs(v,u);
        }
    }
}
int main()
{
    freopen("Dzumbus_Subtask_1.in","r",stdin);
    freopen("Dzumbus_Subtask_1.out","w",stdout);
    int u,v;
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        u=read();
        v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==1)
        {
            dfs(i,0);
            break;
        }
    }
    for(int i=0;i<=1000;i++)
    {
        dp[i][1]=-INF;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1000;j;j--)
        {
            dp[j][0]=max(dp[j][0],dp[j][1]);
            if(j-d[l[i]]>=0)
            {
                dp[j][1]=dp[j-d[l[i]]][1]+1;
                if(j-d[l[i]]-d[l[i-1]]>=0)
                {
                    dp[j][1]=max(dp[j][1],dp[j-d[l[i]]-d[l[i-1]]][0]+2);
                }
            }
            else
            {
                dp[j][1]=-INF;
            }
        }
    }
    for(int i=1;i<=1000;i++)
    {
        dp[i][0]=max(dp[i-1][0],max(dp[i][0],dp[i][1]));
    }
    q=read();
    for(int i=1;i<=q;i++)
    {
        s=read();
        printf("%d\n",dp[s][0]);
    }
}

Subtask 2

由于第二个子任务中的值 $S_{i}$没有额外的约束，因此第一个子任务中的动态规划方案时间和内存都会超出限制。幸运的是，我们可以从不同的角度思考同一件事。我们将修改动态规划状态。状态中的位置P和二进制标志B，其含义与之前相同，但现在，我们要将džumus的数量设为动规的价值，并让其尽可能小，把交换题解的人数将作为动规的其中一维。这些过渡留给读者作为练习~~（但是我把它补上了）~~。

设已经交换题解的人数为 $R$，其余不变，容易推得转移方程为：

$$dp[P][R][0]=\min\{dp[P-1][R][0],dp[P-1][R][1]\}\\dp[P][R][1]=\min\{dp[P-1][R-2][0]+D_{L[P]}+D_{L[P-1]},dp[P-1][R-1][1]+D_{L[P]}\} $$

同样可以通过滚动数组删去第一维。

查询 $S_{i}$ 的答案即查询使得 $\min\{dp[P][R][0],dp[P][R][1]\}\le S_{i}$ 的最大的R。可以使用二分进行查询，时间复杂度为$O(Q\times log_{2}N)$，也可以对询问排序，做离线双指针处理，时间复杂度为$O(Q\cdot log_{2}Q)$，我的代码中是二分的。

这个方法的总时间复杂度是 $O(N^{2})$。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NUM=1005;
const int INF=0x3f3f3f3f3f3f3f3f;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
	{
        if(c=='-')
		{
            f=-1;
        }
		c=getchar();
	}
    while(c>='0'&&c<='9')
	{
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
	}
    return x*f;
}
int n,m,d[NUM],num,head[NUM],ind[NUM],cnt,l[NUM],q,s;
LL dp[NUM][2];
struct edge
{
    int next;
    int to;
}e[NUM*2];
void add_edge(int from,int to)
{
    num++;
    e[num].next=head[from];
    e[num].to=to;
    head[from]=num;
    ind[to]++;
}
void dfs(int u,int fa)
{
    int v;
    l[++cnt]=u;
    for(int i=head[u];i;i=e[i].next)
    {
        v=e[i].to;
        if(v!=fa)
        {
            dfs(v,u);
        }
    }
}
int main()
{
    freopen("Dzumbus_Subtask_2.in","r",stdin);
    freopen("Dzumbus_Subtask_2.out","w",stdout);
    int u,v;
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        u=read();
        v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==1)
        {
            dfs(i,0);
            break;
        }
    }
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=dp[i][1]=INF;
    }
    dp[0][0]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j;j--)
        {
            dp[j][0]=min(dp[j][0],dp[j][1]);
            dp[j][1]=dp[j-1][1]+d[l[i]];
            if(j>1)
            {
                dp[j][1]=min(dp[j-2][0]+d[l[i]]+d[l[i-1]],dp[j][1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=min(dp[i][0],dp[i][1]);
    }
    q=read();
    int left,right,mid,result;
    for(int i=1;i<=q;i++)
    {
        left=0;
        right=n;
        s=read();
        while(left<=right)
        {
            mid=(left+right)>>1;
            if(dp[mid][0]<=s)
            {
                result=mid;
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        printf("%d\n",result);
    }
}

Subtask 3&4

由于本题中的图是无环的，第三和第四个子任务又并未对图的形态进行限制，所以我们可以明确图是一个森林。通过引入一个虚拟根节点 $0$，我们可以将森林简化为一棵树，我们将其视为需要无限džumbus的人，即 $D_{0}=INF$。通过这种方式，我们确保这个人不会影响结果。

我们使用与第二个子任务类似的动态规划解决方案，只是我们是在有根树上进行的。$dp[P][R][B]$的值是使 $P$ 子树中的 $R$ 人交换题解所需的最小džumbus量，和第二个子任务相同的，$B$为 $0$ 时表示处于位置$P$的人并未喝过džumbus， $B$ 为 $1$ 时表示处于位置 $P$ 的人已经喝到了足够džumbus并和别人交换过题解了。

当计算子树的根节点 $P$ 的 $dp$ 值时，我们假设已经计算了整个子树中其他所有节点的 $dp$ 值。我们还需要有一个辅助数组 $dp\_prefix[R][B][K]$，在其状态下保存以 $P$ 为根的子树中至少交换过一次题解的人数为 $R$，到目前为止，我们已经考虑了 $P$ 的前 $K$ 个子节点，并且 $P$ 的状态为 $B$ 时所需的最少džumbus数量。那么很明显 $dp[P][R][B]=dp\_prefix[R][B][P的子节点数]$。设 $C[i]$ 表示节点 $P$ 的第 $i$ 个子节点。

方程的转移是：

$$dp\_prefix[R][0][K]=\min\limits_{i+j=R}\{dp\_prefix[i][0][K−1]+\min\{dp[C[K]][j][0],dp[C[K][j][1]\}\}\\dp\_prefix[R][1][K]=\min\limits_{i+j=R}\begin{cases} dp\_prefix[i-1][0][K−1]+D_{P}+dp[C[K]][j][1]\\dp\_prefix[i-1][0][K−1]+D_{P}+dp[C[K]][j-1][0]+D_{C[K]}\\dp\_prefix[i][1][K−1]+dp[C[K]][j][1]\\dp\_prefix[i][1][K−1]+dp[C[K]][j-1][0]+D_{C[K]}\\dp\_prefix[i][1][K−1]+dp[C[K]][j][0]\end{cases} $$

（读者应仔细分析实施细节和角落案例）（但我又补了）。

易发现 $dp\_prefix$ 数组的第三位可以滚动掉，滚动掉后 $dp\_prefix$ 数组其实是多余的。

$$dp[P][R][0]=\min\limits_{i+j=R}\{dp[P][i][0]+\min\{dp[C[K]][j][0],dp[C[K][j][1]\}\}\\dp[P][R][1]=\min\limits_{i+j=R}\begin{cases} dp[P][i-1][0]+D_{P}+dp[C[K]][j][1]\\dp[P][i-1][0]+D_{P}+dp[C[K]][j-1][0]+D_{C[K]}\\dp[P][i][1]+dp[C[K]][j][1]\\dp[P][i][1]+dp[C[K]][j-1][0]+D_{C[K]}\\dp[P][i][1]+dp[C[K]][j][0]\end{cases} $$

当我们将所有节点上的所有状态相加时，我们在 $dp$ 中得到了总共 $O(n^{2})$ 个状态，并且每个转换最多以 $O(n)$ 个步骤计算。因此，时间复杂度貌似是 $O(n^{3})$ 。

但实际上解决方案的时间复杂度是 $O(n^{2})$的 （我不理解为什么要分两个子任务，反正我按官方题解来的）。

显然，一棵子树上根节点的解决方案数不可能超过该子树的规模。因此，在计算 $dp\_prefix$ 时，不必检查 $A$ 和 $B$ 的所有选项，只检查那些可能的选项（$A$ 不能大于已处理子级的子树大小之和增加 $1$，$B$ 不能大于当前子级的子树大小）。我们将证明每个子树的计算的总复杂度最多为 $O(子树大小)$。

这个证明取决于树的深度。

首先，这种说法显然适用于叶子结点。

其次，让我们构建一个非叶子节点，并假设我们已经计算了具有上述复杂度的子节点的 $dp$ 值。假设该节点有 $x$ 个子节点，其子树大小为 $Y_{1},Y_{2}......Y_{x}$。计算该节点及其子树的 $dp$ 值的总复杂度可以表示为：

$$\begin{aligned} O(\sum\limits_{i=1}^{x} Y_{i}^{2}+\sum\limits_{i=1}^{x} (1+\sum\limits_{j=1}^{i-1} Y_{j}) \cdot Y_{i}) &= O(\sum\limits_{i=1}^{x} Y_{i}^{2}+\sum\limits_{i=1}^{x} Y_{i}+\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i-1} Y_{i}\cdot Y_{j}) \\ &= O(1+\sum\limits_{i=1}^{x} Y_{i}^{2}+2\sum\limits_{i=1}^{x} Y_{i}+2\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i-1} Y_{i}\cdot Y_{j}) \\ &= O((1+\sum\limits_{i=1}^{x} Y_{i})^{2}) \\ &= O(子树大小^{2}) \end{aligned} $$

因此，整个解的总时间复杂度为 $O(n^{2})$。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned int UI;
const UI INF=1000000001;
const int NUM=1005;
int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
	{
        if(c=='-')
		{
            f=-1;
        }
		c=getchar();
	}
    while(c>='0'&&c<='9')
	{
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
	}
    return x*f;
}
int n,m,num,head[NUM],y[NUM],q,s;
UI dp[NUM][NUM][2],d[NUM];
struct edge
{
    int next;
    int to;
}e[NUM*3];
void add_edge(int from,int to)
{
    num++;
    e[num].next=head[from];
    e[num].to=to;
    head[from]=num;
}
void dfs(int u)
{
    int v;
    y[u]=1;
    dp[u][0][0]=0;
    for(int h=head[u];h;h=e[h].next)
    {
        v=e[h].to;
        if(!y[v])
        {
            dfs(v);
            for(int i=y[u];i>=0;i--)
            {
                for(int j=y[v];j>=0;j--)
                {
                    dp[u][i+j][0]=min(dp[u][i+j][0],min(dp[u][i][0]+min(dp[v][j][0],dp[v][j][1]),INF));
                    dp[u][i+j][1]=min(dp[u][i+j][1],min(dp[u][i][1]+min(dp[v][j][0],dp[v][j][1]),INF));
                    if(j) dp[u][i+j][1]=min(dp[u][i+j][1],min(dp[u][i][1]+dp[v][j-1][0]+d[v],INF));
                    if(i) dp[u][i+j][1]=min(dp[u][i+j][1],min(dp[u][i-1][0]+d[u]+dp[v][j][1],INF));
                    if(i&&j) dp[u][i+j][1]=min(dp[u][i+j][1],min(dp[u][i-1][0]+d[u]+dp[v][j-1][0]+d[v],INF));
                }
            }
            y[u]+=y[v];
        }
    }
}
int main()
{
    freopen("Dzumbus_Subtask_34.in","r",stdin);
    freopen("Dzumbus_Subtask_34.out","w",stdout);
    int u,v;
    n=read();
    m=read();
    d[0]=INF;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        d[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        u=read();
        v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        add_edge(0,i);
    }
    dfs(0);
    for(int i=n;i>=0;i--)
    {
        dp[0][i][0]=min(dp[0][i+1][0],dp[0][i][0]);
    }
    q=read();
    int left,right,mid,result;
    for(int i=1;i<=q;i++)
    {
        left=0;
        right=n;
        s=read();
        while(left<=right)
        {
            mid=(left+right)>>1;
            if(dp[0][mid][0]<=s)
            {
                result=mid;
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        printf("%d\n",result);
    }
}