题解 P2405 non天平

PanH · 2020-07-03 14:23:07 · 题解

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

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

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

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

把柿子拎出来：

拆，移：

发现我们在计算的时候维护一个最小的 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;
}