题解 P3286 【[SCOI2014]方伯伯的商场之旅】

· · 题解

思路

广告：希丰展

如果你做过这道题的话可以想到选择石子位置的中位数一定是最优的。

但是本题对于并无卵用，因为无法同时处理很多数字，只能单个处理。（建议写暴力）

对于本题的时空限制来说显然枚举每个数是不现实的。但显然数位数不会很多，可以考虑枚举贪心，整体处理（前缀和的形式）。首先把第一个位置当作集合点，算出一个贡献。然后向右枚举，更新贡献。

可以看出这是一个单峰函数，当集合点右移的时候，如果新的答案更小，就更新答案，否则就不变。

举个栗子：把二号点转移到三号点，变动的就是：小于等于二号点的石子个数 - 大于等于三号点的石子个数。如果这个值是负的，我们就更新。

为什么贪心是正确的？因为前面的石子数量和一直在增加，而其后的一直在减小，因此答案的减小值一定是不断减小的。

先用一遍数位 DP 求出集合点在一号点的答案，然后向右枚举转移即可。当枚举到 n 的时候就结束了。

代码

不会真的有人数位 DP 写递推吧，不会吧不会吧不会吧。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int L,R,K;
int a[100],f[100][10000];

int dfs(int now,int sum,int p,int lim){
    if(!now)return max(sum,0LL)
    if(!lim&&~f[now][sum])return f[now][sum];
    int ans=0;
    int num=lim?a[now]:K-1;
    for(int i=0;i<=num;i++)
        ans+=dfs(now-1,sum+(p==1?i*(now-1):(now<p?-i:i)),p,lim&&(i==num));
    if(!lim)f[now][sum]=ans;
    return ans;
}

inline int Solve(int x){
    int n=0;
    while(x){
        a[++n]=x%K;
        x/=K;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(f,-1,sizeof(f));
        ans+=((i==1)?1:-1)*dfs(n,0,i,1);
    }
    return ans;
}

signed main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%lld%lld%lld",&L,&R,&K);
    printf("%lld",Solve(R)-Solve(L-1));
    return 0;
}