洛谷P3286 [SCOI2014]方伯伯的商场之旅

时间:2021-09-22 19:00:03

题目:洛谷P3286 [SCOI2014]方伯伯的商场之旅

思路

数位DP

dalao说这是数位dp水题,果然是我太菜了...
自己是不可能想出来的。这道题在讲课时作为例题,大概听懂了思路,简单复述一下。
首先根据数据范围和部分题意,不难看出是数位dp。
但是和常规的数位dp不同,我们并不知道每个数字最后的集结点。
于是我们不妨钦定所有石子最后都聚在最低位(第一位)。此时的总代价记作\(cost\),可以通过一次简单的数位dp得到。
但这样显然不是最优解,对于有的数,石子聚在更高位代价更少。于是我们就逐位移动。
比如说对于数字\(i\),石子现在都聚在第一位(最低位),要把石子移到第二位,那么\(i\)的第二位及更高位移动的代价减少,\(i\)的第一位移动代价增加,类似树形dp中的换根dp。
\(delta(i)\)表示 数字i的石子 从 聚在第一位 移至 聚在第二位,花费的代价 的 减少量(这句话有点长)。
\(delta(i)<0\)时,说明花费的代价没有减少,反而增加了,那么我们就不移动i的石子,否则把i的石子都移至第二位。基于上述操作,现在的总花费为\(cost-\sum_{i=l}^r \max(delta(i),0)\)
式子中的\(\sum_{i=l}^r \max(delta(i),0)\)可以再用一次数位dp计算(类似换根dp的第二次dp)。
现在只是把能移的石子都从第一位移到第二位,之后再按上述方法,把能移的石子从第二位移到第三位、从第三位移到第四位...最后所有石子都被移到了最优的位置

可以结合代码理解。


Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,k,a[80],dp[80][4000][2][2];
ll dfs(int pos,int sum,bool lead,bool limit){
    if(pos==0) return sum;
    ll &ans=dp[pos][sum][lead][limit];
    if(ans!=-1) return ans;
    ans=0;
    for(int i=0,up=limit?a[pos]:k-1;i<=up;++i){
        if(!i&&lead) ans+=dfs(pos-1,0,true,limit&&i==a[pos]);
        else ans+=dfs(pos-1,sum+i*(pos-1),false,limit&&i==a[pos]);
    }
    return ans;
}
ll dfs(int to,int pos,int sum,bool lead,bool limit){
    if(pos==0) return max(sum,0);
    ll &ans=dp[pos][sum+500][lead][limit];
    if(ans!=-1) return ans;
    ans=0;
    for(int i=0,up=limit?a[pos]:k-1;i<=up;++i){
        if(!i&&lead) ans+=dfs(to,pos-1,0,true,limit&&i==a[pos]);
        else if(pos>=to) ans+=dfs(to,pos-1,sum+i,false,limit&&i==a[pos]);
        else ans+=dfs(to,pos-1,sum-i,false,limit&&i==a[pos]); 
    }
    return ans;
}
ll solve(ll num){
    memset(dp,-1,sizeof(dp));
    int len=0;
    while(num) a[++len]=num%k,num/=k;
    ll res=dfs(len,0,true,true);
    for(int i=2;i<=len;++i){
        memset(dp,-1,sizeof(dp));
        res-=dfs(i,len,0,true,true);
    }
    return res;
}
int main(){
    scanf("%lld%lld%d",&l,&r,&k);
    printf("%lld\n",solve(r)-solve(l-1));
    return 0;
}