首页 > 其他分享 >luogu P7201 [COCI2019-2020#1] Džumbus题解

luogu P7201 [COCI2019-2020#1] Džumbus题解

时间：2022-11-18 19:11:28浏览次数：92  
标签：limits COCI2019 min int 题解 prefix luogu dp

须知

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

基本信息

任务名：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);
    }
}

标签：limits,COCI2019,min,int,题解,prefix,luogu,dp
From： https://www.cnblogs.com/looking-forward-to-tomorrow/p/16904682.html

相关文章

  • P5999 [CEOI2016] kangaroo 蓝 题解
    前言有些题目照常DP不是很好做，感觉像是区间DP，但是怎么设状态都不好转移，那么可以考虑一种维护块儿的DP，就是这道题要用到的知识点。背景分析如果每次跳跃的点的编号形......
  • LUOGU P1363 幻象迷宫
    题干就用这个题来思路开阔一下吧这个题解的hack数据解释的很好，思路解释也不错这个题解的代码写的不错我是第一个题解的第二个错误思路，然后T了9个点，开$O_2$MLE，冲了好几......
  • 恒创科技：有关服务器虚拟化的常见问题解答
    虚拟化”一词经常使用，尤其是与服务器相关的时候。以下是一些有关服务器虚拟化常见问题的解答。什么是服务器虚拟化?虚拟化是一个经常应用于范围广泛的......
  • helm 问题解决 —— HELM部署异常：Error: UPGRADE FAILED: another operation (install
    转载： https://blog.csdn.net/dreamer_chen/article/details/118596034  HELM部署异常：Error:UPGRADEFAILED:anotheroperation(install/upgrade/rollback)isin......
  • luoguP1269 信号放大器
    神奇的题目想了3个做法假·贪心、真·DP、真·贪心全部交上去分别获得40、90、100的好成绩蚌埠住了1.假·贪心考虑从孩子节点开始一直到指定的根节点u到中途某个节......
  • week4题解
    1.深度优先搜索   思路：以固定的移动顺序走迷宫，若能到终点则记一次到终点后回溯到前一个有分岔的地方，走另一条路线若走到死路也同样回溯到前一个有分叉的地方。最......
  • DTOJ-2022-11-10-测试-题解
    题目链接ABCA这个套路已经出现了很多次了就是两条线之间的网格图路径数，做法呢就是容斥题意求满足以下条件的\(n\timesm\)的矩阵的个数对\(10^9+7\)取模对于......
  • vue 项目源码映射失败问题解决
    目录vue项目源码映射失败问题解决前言解决方案效果参考vue项目源码映射失败问题解决前言不知何时起，项目控制台调试进入源代码变成编译后的文件了，调试起来十分不便，强迫......
  • 服务商系统集中高频交易CPU飙升问题解决优化过程
    通过创建数据表索引，有效提升系统性能。一、问题背景在11月10日下午5点，出现channel异步下发消息队列消息积压报警，经排查分析是因为channel请求鑫某亿服务商落单时间过长......
  • Ubuntu常见问题解决
    Ubuntu常见问题解决1.ubuntu系统上安装qt5.12后无法调试运行 原因：缺少gcc、g++、make、libgl1sudoapt-getinstallgccsudoapt-getinstallg++sudoapt-getinstallmak......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99