自动搬运

查看原文

来自洛谷，原作者为

	Lyrith_with_xQ 与你的日常，便是 ⌈ 奇迹 ⌋

搬运于2025-08-24 23:13:16，当前版本为作者最后更新于2025-04-13 09:02:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，读题！

形式化题意

给出一个长 $n$ 的数组 $a$ 和一个数 $k$，设有一个长 $n$ 的数组 $p$ 满足 $2^k\mid\prod^n_{i=1}(a_i+p_i)$ 并且 $a_i+p_i\le10^5$，求 $\sum^n_{i=1}p_i$，如果数组 $p$ 不存在，输出 $-1$。

思路

考虑用 dp 解题。

定义 $dp_{i,j}$ 表示使得 $2^j\mid\prod^i_{k=1}(a_k+p_k)$ 的最小 $\sum^i_{k=1}p_k$ 的值，设最小的比 $x$ 大的 $2^y$ 的倍数减去 $x$ 的值为 $f(x,y)$。

于是用瞪眼法（？）可以得出 $dp_{1,i}=f(1,i)$。

可以发现，对于 $dp_{i,j}$ 可以枚举 $a_i$ 要分担的 $2$ 的个数，设 $a_i$ 要分担 $x$ 个 $2$，则状态转移方程可以写为 $dp_{i,j}=\min_{0\le x\le j}\{dp_{i-1,j-x}+f(i,x)\}$。

可是这是三重循环，会超时，考虑优化。

可以发现，当 $x$ 过大时，因为 $a_i+p_i\le 10^5$ 的限制，$f(i,x)+dp_{i-1,j-x}$ 便不符合条件，因此只用从 $0$ 枚举到 $\min\{\lfloor\log_2(10^5)\rfloor,j\}$ 即可。

于是状态转移方程变为 $dp_{i,j}=\min_{0\le x\le \min\{\lfloor\log_2(10^5)\rfloor,j\}}\{dp_{i-1,j-x}+f(i,x)\}$。

虽然这还是三重循环，但因为 $2^x$ 增长很快，所以第三重循环的时间复杂度是常数。

接下来回头再考虑 $f(x,y)$ 如何实现。

当 $x\le 2^y$ 时，显然可得 $f(x,y)=2^y-x$。

当 $x>2^y$ 时，$f(x,y)=2^y\times\lceil\frac{x}{2^y}\rceil$。

代码

#include<bits/stdc++.h>
using namespace std;

int n,k,a[505],dp[505][5005],f[505][5005];

int pow2(int a){return 1<<a;}

int find(int x,int k)//函数f(x,y) 
{
	if(k>=ceil(log2(1e5)))return 1e8;//2^k大于1e5，无解
	int r=ceil(log2(x));
	if(r<k)return pow2(k)-x;
	else
	{
		int a=ceil(1.0*x/pow2(k));
		if(pow2(k)*a>1e5)return 1e8;//答案大于1e5，无解
		return pow2(k)*a-x;
	}
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)dp[i][j]=1e8,f[i][j]=find(a[i],j);//预处理 
	}
	for(int i=0;i<=k;i++)dp[1][i]=f[1][i];//初始状态 
	for(int i=2;i<=n;i++)//dp过程
	{
		for(int j=0;j<=k;j++)
		{
			for(int l=0;l<=min((int)floor(log2(1e5)),j);l++)dp[i][j]=min(dp[i][j],dp[i-1][j-l]+f[i][l]);
		}
	}
	printf("%d",dp[n][k]==1e8? -1:dp[n][k]);//注意无解的情况 
	return 0;//代码后加return 0;是好习惯 
} 

性能分析

时间复杂度：$O(nk)$。

空间复杂度：$O(nk)$。

可以通过本题。