这道题我想不到怎么dp…
所以写了个贪心
算法1
首先,我们考虑如何让最后一位相等
因为最后一位不受其他数字进位的影响。
当n=1时,答案为c(a,b)=min(a-b+10,b-a+10,abs(a-b))
a-b+10,b-a+10,abs(a-b)三种方案为进位,退位,直接过去
当n>1时,就不能只考虑当前位了,因为当前位的进位会影响到前面的,造成一定影响
(可能是好的或坏的)
思考一下,一个结论:当前位的进位只可能使得到 前面的位的答案 加或减一
另一个结论:当前位的进位只可能影响到 前面的那个数的c函数(更前面的位这时不受影响)
它们我还不太会数学证明,感性上是对的
所以要选哪种方案?进位,退位,直接过去?
只要分别加上各自的
潜在贡献
然后取最小值即可。
int u=(10-a[i])+b[i]+(c(a[i-1]+1,b[i-1])-c(a[i-1],b[i-1]));
int d=a[i]+(10-b[i])+(c(a[i-1]-1,b[i-1])-c(a[i-1],b[i-1]));
int g=abs(a[i]-b[i]);
选择min(u,d,g)
势能分析
有人可能觉得n次进位的模拟会超时,
其实不会。
每次进位会使得数码的数字和减去8
由于和不为负,且每次加一操作使数字和加一,
所以进位最多为O(n)次
C++ 代码
#include<bits/stdc++.h>
const int N = 1e6 + 33,inf=2e9;
int c(int i,int j){
i%=10,j%=10;
if(i>j)swap(i,j);
return min(j-i,i+10-j);
}
int n,a[N],b[N];
int*f,*g;
void up(int i){
f[i]++;
while(1<=i&&f[i]==10){
f[i]=0;
f[--i]++;
}
}void down(int i){
f[i]--;
while(1<=i&&f[i]==-1){
f[i]=9;
f[--i]--;
}
}
int main() {
rd(n);
fr(i,1,n){
scanf("%1d",&a[i]);
}
fr(i,1,n){
scanf("%1d",&b[i]);
}
f=a,g=b;
int ans=0;
rf(i,n,1){
int ori=c(a[i-1],b[i-1]);
int u=(10-a[i])+b[i]+(c(a[i-1]+1,b[i-1])-ori);
int d=a[i]+(10-b[i])+(c(a[i-1]-1,b[i-1])-ori);
int g=abs(a[i]-b[i]);
if(u<=min(d,g)){
ans+=(10-a[i])+b[i];
up(i-1);
}else if(d<=min(u,g)){
ans+=a[i]+(10-b[i]);
down(i-1);
}else{
ans+=g;
}
}
pt("%d\n",ans);
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
🐮