【洛谷 2405】 non天平

题目背景

non最近正在为自己的体重而苦恼，他想称量自己的体重。于是，他找来一个天平与许多砝码。

题目描述

砝码的重量均是n的幂次，n^1、n^2、n^3、n^4、n^5的……non想知道至少要多少个砝码才可以称出他的重量m。注意砝码可以放左边，也可以放右边。

输入输出格式

第一行一个正整数m，表示non的重量；

第二行一个正整数n，表示砝码重量幂次的底；

一个整数表示最少所需的砝码数。

输入输出样例

99
10

2

说明

【数据范围】

对于30%的数据点，m <= 2^63 - 1

对于100%的数据点，0 <= m <= 10^10000, 0 < n <= 10000

分析：对于本题的数据范围，势必要高精了。

首先说明白一点：天平使用原则：左物右码。

那么题目可以等效成这样：右边的质量-左边的质量=给出的质量，所以砝码就有了加减两个策略可以选择

我们先来看题目的样例：99

99的得出有两种大的方向：加策略 和 减策略

首先加策略的话，需要9*10+9*1 ->18个

其次减策略的话，需要1*100-1*1 ->2个

样例减策略要优于加策略。

原题目也就等价于这样一个等式

k0*10^0+k1*10^1+k2*10^2+k3*10^3=99 这里我们假设左边就三项把 方便研究

k的系数可正可负，正就是放在右边，负就是放在左边。

那么我们要求∑|k|最小，可以这样想： 我们先考虑最小的质量是1的砝码，我们要确定使用了几个1砝码，那么我们就要把个位的9补平，要么是10-1，需要一个； 要么是0+9，需要9个；

显然减一下好，而且减掉一个刚好。于是我们确定了上述方程的第一项系数k0= -1

那么方程就是这样：-1*10^0+k1*10^1+k2*10^2+k3*10^3=99

把第一项移到右边：k1*10^1+k2*10^2+k3*10^3=100

我们看到我们成功的把个位填平了，使得方程可以同除以10

那么就变成了k1*10^0+k2*10^1+k3*10^2=10

于是到这里我们看到了问题具有很强的 最优子结构性质。

而无后效性是显然的，我们确定了小法吗的个数后，右边的个位被填平，所以我们不在需要小法吗

于是问题就是一道DP问题。

而这个m是一个高精数，在说我们的n=10是很特殊的，对于其他的n我们 要进行很多的 m div n 和m mod n操作

于是我们整体的预处理一下，

把m进行n进制的分解

不断的把 计算m mod n这个余数，记录，再把m div n，把m除干净为止；

于是我们得到了n进制下的 每一位上的数字，对应于我们每一个数量级的砝码

对于每一位我们有两个策略，直接使用yu【i】这么多的砝码，或者用n-yu【i】这么多的砝码进上去，两种操作都可以使n进制下的个位变成0

于是我们发现他其实是0/1 DP 也就是说我们开一个数组f【0..m,0..1】，前一维意思是处理到n进制下的第i位，后一维意思是我们当前这一位的处理策略 0代表直接拿出yu【i】这么多的砝码，1代表我们把当前位补平，进到下一位去

数组元素存储处理完当前第i位需要的砝码数

于是状态转移方程：

f[i,0]:=min(f[i-1,0]+yu[i],f[i-1,1]+yu[i]+1);

f[i,1]:=min(f[i-1,0]+b-yu[i],f[i-1,1]+b-yu[i]-1);

写状态转移方程的时候仔细一点就不会错：使用f【i-1，1】的时候，我们当前位就+1

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
char cl[10005];
int head,ym[10005],m[10005],n,h[10005],laji[10005];
int ln,lm,tail,f[500005][2];
void deal()//转N进制。
{
 int i;
 while(1)
 {
      int u=0;
      tail=-1;
      int yu=0;
    for(i=0;i<lm;i++)
    {
          tail++;
        u=yu*10+m[i];
          h[tail]=u/n;
          yu=u%n;
    }
      head++;
      ym[head]=yu;
    for(i=0;i<lm;i++)
      if(h[i]!=0) break;
    for(int j=i;j<lm;j++)
      m[j-i]=h[j];
    lm-=i;
    if(lm<=ln) { 
                 int po=0;
                 for(i=0;i<lm;i++)
                    po=po*10+m[i];
                 head++;
                 ym[head]=po%n;
                 po=po/n;
                 head++;
                 ym[head]=po;
                 break;
               }
    }
}
int main()
{
   cin>>cl;
   lm=strlen(cl);
   cin>>n;
   if(n==1) cout<<cl;
   else 
   {
    for(int i=0;i<lm;i++)
      m[i]=cl[i]-'0'; 
    deal();
    int ans=0;
    f[0][1]=1;
    for(int i=1;i<head;i++)
     {
         f[i][0]=min(f[i-1][0]+ym[i],f[i-1][1]+ym[i]+1);
         f[i][1]=min(f[i-1][0]+n-ym[i],f[i-1][1]+n-ym[i]-1);
     }
    cout<<min(f[head-1][0],f[head-1][1]);
    }
    return 0;
}