须知
本题解骨架是本人由官方题解翻译得来的,并补充了一些不详细的地方,修改了一些错误,自己写了每一个子任务的代码(因为官方题解代码和文本不太匹配)。
基本信息
任务名: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