Description
Input
HINT
1 < = L < = R < = 10^15, 2 < = K < = 20
Solution
说白了,这个题就是给了L~R的数,每个数的每个数位是一堆石子,把这堆石子合成一个位置,求总的最小代价。
法一:GZZ法
发现,对于一个数字P,假设钦定最终合并位置是p,
调整的时候,p向左移动一位,代价变化是p及右边所有的数位和-p左边所有数位和。
p向右移动一位,代价变化是p及左边所有数位和-p右边所有数位和。
设最优的位置的数字是x,位置是p,p左边数位和是a,右边是b
那么,一定有不等式:x+a-b>=0 ; x+b-a>=0 就是说,x不论往左往右移动,代价的变化总是增大的。
即:-x<=a-b<=x
所以,如果知道最终填的a-b,和x,p,就可以判断这个p位置填x是不是左边a,右边b的最优解了。
枚举p,x;
伪代码:(cnt是最高位,进制用m,填数用k)
for(p=1~cnt)
for(x=0~m-1)
for(i=cnt~1)
for(a-b=-200~+200)
设f[i][a-b][0/1]表示,填完第i位,a-b的值,有没有限制情况下,所有符合情况的数移动到p位置所花费的代价。
g[i][a-b][0/1]表示,f的方案数,即满足情况的数的个数,方便转移。
if(i==p){
continue;
}
for(k=0;k<m;k++){
if(i<p)
else
}
在i循环完之后,
for(a-b=-200~+200)
if(-x<=a-b<x) ret+=f[1][a-b][0/1]
注意这里是<=和<,因为可能一个数字有两个位置都是最优的合并位置,只能算一遍。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
const int M=;
const int fix=;
const int up=;
ll f[N][][];
ll g[N][][];
ll L,R;
int m;
ll ansl,ansr;
int a[N],cnt;
ll wrk(){
ll ret=;
for(int p=;p<=cnt;p++){
for(int x=;x<m;x++){
memset(f,,sizeof f);
memset(g,,sizeof g);
g[cnt+][fix][]=;
for(int i=cnt;i>=;i--){
for(int j=;j<=up;j++){
if(i==p){
if(x<a[i]){
if(g[i+][j][]) g[i][j][]+=g[i+][j][],f[i][j][]+=f[i+][j][];
if(g[i+][j][]) g[i][j][]+=g[i+][j][],f[i][j][]+=f[i+][j][];
}
else if(x==a[i]){
g[i][j][]+=g[i+][j][],f[i][j][]+=f[i+][j][];
g[i][j][]+=g[i+][j][],f[i][j][]+=f[i+][j][];
}
else{
g[i][j][]+=g[i+][j][],f[i][j][]+=f[i+][j][];
}
continue;
} for(int k=;k<m;k++){
if(i>p){//before
if(j+k>up) continue; if(k<a[i]){
g[i][j+k][]+=g[i+][j][],f[i][j+k][]+=f[i+][j][]+(i-p)*k*g[i+][j][];
g[i][j+k][]+=g[i+][j][],f[i][j+k][]+=f[i+][j][]+(i-p)*k*g[i+][j][];
}
else if(k==a[i]){
g[i][j+k][]+=g[i+][j][],f[i][j+k][]+=f[i+][j][]+(i-p)*k*g[i+][j][];
g[i][j+k][]+=g[i+][j][],f[i][j+k][]+=f[i+][j][]+(i-p)*k*g[i+][j][];
}
else{
g[i][j+k][]+=g[i+][j][],f[i][j+k][]+=f[i+][j][]+(i-p)*k*g[i+][j][];
}
}
else{//after
if(j-k<) continue; if(k<a[i]){
f[i][j-k][]+=f[i+][j][]+g[i+][j][]*(p-i)*k,g[i][j-k][]+=g[i+][j][];
f[i][j-k][]+=f[i+][j][]+g[i+][j][]*(p-i)*k,g[i][j-k][]+=g[i+][j][];
}
else if(k==a[i]){
f[i][j-k][]+=f[i+][j][]+g[i+][j][]*(p-i)*k,g[i][j-k][]+=g[i+][j][];
f[i][j-k][]+=f[i+][j][]+g[i+][j][]*(p-i)*k,g[i][j-k][]+=g[i+][j][];
}
else{
f[i][j-k][]+=f[i+][j][]+g[i+][j][]*(p-i)*k,g[i][j-k][]+=g[i+][j][];
}
}
}
}
}
for(int j=;j<=up;j++){
if((fix-x<=j)&&(j<x+fix)){
ret+=f[][j][]+f[][j][];
}
}
}
}
return ret;
}
int main(){
scanf("%lld%lld",&L,&R);
scanf("%d",&m);
L--;
cnt=;
while(L){
a[++cnt]=L%m;
L/=m;
}
if(cnt==){
ansl=;
}
else{
ansl=wrk();
} cnt=;
while(R){
a[++cnt]=R%m;
R/=m;
}
ansr=wrk();
printf("%lld",ansr-ansl);
}
法二:大众法。
直接钦定1号位置是最优位置,计算出来所有的总和ans
调整。
枚举位置p从2~cnt,表示要计算从p-1移动到p,会有多少个数的代价减少多少。
代价就是,sum(1,p-1)-sum(p,cnt)
设f[i][a-b][0/1]表示,第i位,这个sum的差值,有没有限制情况下,多少个数符合这个情况。
循环完一个p之后,
把a-b<0的f,ans-=(a-b)*f[i][a-b][0/1]
a-b>=0的不管。
这样进行cnt次,一定可以把所有的数移动到最优解的位置。
网上题解很多,代码就不贴了。(我也没写)