[SCOI2014]方伯伯的商场之旅

枫林晚

2018-08-23 22:35:15

Solution

**博客园cnblog链接:[[SCOI2014]方伯伯的商场之旅](https://www.cnblogs.com/Miracevin/p/9526948.html)** 网上的做法基本都是贪心到1号位置,再容斥。 这里我就写一个不一样的做法。直接就可以得到答案。 (其实是我们学长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) ```cpp 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]  注意这里是<=和<,因为可能一个数字有两个位置都是最优的合并位置,只能算一遍。 ``` ## Code: ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=70; const int M=22; const int fix=201; const int up=402; ll f[N][405][2]; ll g[N][405][2]; ll L,R; int m; ll ansl,ansr; int a[N],cnt; ll wrk(){ ll ret=0; for(int p=1;p<=cnt;p++){ for(int x=0;x<m;x++){ memset(f,0,sizeof f); memset(g,0,sizeof g); g[cnt+1][fix][1]=1; for(int i=cnt;i>=1;i--){ for(int j=0;j<=up;j++){ if(i==p){ if(x<a[i]){ if(g[i+1][j][0]) g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0]; if(g[i+1][j][1]) g[i][j][0]+=g[i+1][j][1],f[i][j][0]+=f[i+1][j][1]; } else if(x==a[i]){ g[i][j][1]+=g[i+1][j][1],f[i][j][1]+=f[i+1][j][1]; g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0]; } else{ g[i][j][0]+=g[i+1][j][0],f[i][j][0]+=f[i+1][j][0]; } continue; } for(int k=0;k<m;k++){ if(i>p){//before if(j+k>up) continue; if(k<a[i]){ g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0]; g[i][j+k][0]+=g[i+1][j][1],f[i][j+k][0]+=f[i+1][j][1]+(i-p)*k*g[i+1][j][1]; } else if(k==a[i]){ g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0]; g[i][j+k][1]+=g[i+1][j][1],f[i][j+k][1]+=f[i+1][j][1]+(i-p)*k*g[i+1][j][1]; } else{ g[i][j+k][0]+=g[i+1][j][0],f[i][j+k][0]+=f[i+1][j][0]+(i-p)*k*g[i+1][j][0]; } } else{//after if(j-k<0) continue; if(k<a[i]){ f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0]; f[i][j-k][0]+=f[i+1][j][1]+g[i+1][j][1]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][1]; } else if(k==a[i]){ f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0]; f[i][j-k][1]+=f[i+1][j][1]+g[i+1][j][1]*(p-i)*k,g[i][j-k][1]+=g[i+1][j][1]; } else{ f[i][j-k][0]+=f[i+1][j][0]+g[i+1][j][0]*(p-i)*k,g[i][j-k][0]+=g[i+1][j][0]; } } } } } for(int j=0;j<=up;j++){ if((fix-x<=j)&&(j<x+fix)){ ret+=f[1][j][0]+f[1][j][1]; } } } } return ret; } int main(){ scanf("%lld%lld",&L,&R); scanf("%d",&m); L--; cnt=0; while(L){ a[++cnt]=L%m; L/=m; } if(cnt==0){ ansl=0; } else{ ansl=wrk(); } cnt=0; while(R){ a[++cnt]=R%m; R/=m; } ansr=wrk(); printf("%lld",ansr-ansl); } ```