自动搬运

查看原文

来自洛谷，原作者为

	PanH AFO!?!

搬运于2025-08-24 21:37:20，当前版本为作者最后更新于2020-07-03 14:23:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

我来水题解提供另一种转移方程。

设 $f[i]$ 为前 $i$ 位（从高到低）全部解决的最小使用砝码数量。

$$f[i]=\min(f[i-1]+a[i],f[j]+(n-1)\cdot(i-j)+2-\sum_{k=j+1}^{i}a[k]) $$

意思是先枚举每一位，再枚举有多少进位，这些位置一起进位时对答案的贡献就是 $(n-1)\cdot(i-j)+2-\sum_{k=j+1}^{i}a[k]$ 。

计算前缀和后是 $O(n^2)$ 的，虽然也可以过（高精可能才是复杂度瓶颈），但显然可以优化成 $O(n)$ 。

把柿子拎出来：

$$f[i]=f[j]+(n-1)\cdot(i-j)+2-sum[i]+sum[j]$$

拆，移：

$$f[i]-n\cdot i+i+sum[i]=f[j]-n\cdot j+j+sum[j]+2$$

发现我们在计算的时候维护一个最小的 $f[j]-n\cdot j+j+sum[j]$ 就彳亍了。

高精部分我就不讲了吧，别的题解好像挺清楚的。。。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[100005];
int n,a[5000005],f[5000005],sum[5000005],tot;
signed main()
{
   scanf("%s%lld",s+1,&n);
   if(n==1)
   {
   	printf("%s",s+1);
   	return 0;
   }
   int m=strlen(s+1);
   for(int j=1;j<=m;j++)
   {
   	int p=0;
   	for(int i=1;i<=tot;i++)
   		a[i]=a[i]*10+p,p=a[i]/n,a[i]%=n;
   	while(p)	a[++tot]=p%n,p/=n;
   	p=s[j]-'0';
   	for(int i=1;i<=tot;i++)
   	{
   		a[i]+=p,p=a[i]/n,a[i]%=n;
   		if(!p)	break;
   	}
   	while(p)	a[++tot]=p%n,p/=n;
   }
   for(int i=1;i<=tot;i++)	sum[i]=sum[i-1]+a[i];
   for(int i=1,minn=0;i<=tot;i++)
   {
   	f[i]=f[i-1]+min(a[i],n-a[i]+1);
   	f[i]=min(f[i],minn+n*i-i-sum[i]+2);
   	minn=min(minn,f[i]-n*i+i+sum[i]);
//		for(int j=0;j<i;j++) //O(n^2)
//			f[i]=min(f[i],f[j]+n*(i-j)-sum[i]+sum[j]-i+j+2);
   }
   printf("%lld",f[tot]);
   return 0;
}