bzoj3598: [Scoi2014]方伯伯的商场之旅【数位dp】

Description

方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧，位置在 i 的人面前的第 j 堆的石子的数量，刚好是 i 写成 K 进制后的第 j 位。
现在方伯伯要玩一个游戏，商场会给方伯伯两个整数 L,R。方伯伯要把位置在 [L, R] 中的每个人的石子都合并成一堆石子。每次操作，他可以选择一个人面前的两堆石子，将其中的一堆中的某些石子移动到另一堆，代价是移动的石子数量 * 移动的距离。商场承诺，方伯伯只要完成任务，就给他一些椰子，代价越小，给他的椰子越多。所以方伯伯很着急，想请你告诉他最少的代价是多少。
例如：10 进制下的位置在 12312 的人，合并石子的最少代价为：
1 * 2 + 2 * 1 + 3 * 0 + 1 * 1 + 2 * 2 = 9
即把所有的石子都合并在第三堆

Input

输入仅有 1 行，包含 3 个用空格分隔的整数 L，R，K，表示商场给方伯伯的 2 个整数，以及进制数

Output

输出仅有 1 行，包含 1 个整数，表示最少的代价。

Sample Input

3 8 3

Sample Output

HINT

1 < = L < = R < = 10^15, 2 < = K < = 20

解题思路：

感觉自己学了假的数位dp。

不妨先算全挪到第一位的概率，这个很好算，f[pos][sum]表示到第pos位，花费为sum的方案数，如果当前位为j，很明显将会有对sum有j*(pos-1)的贡献，转移即可。

注意到对于一个数字，集结点从1~i的花费为一个单峰函数，比如集结点从i转移到i+1，花费将会加上i左边的数字和，减去i右边的数字和，那么我们就从2~i枚举集结点，计算这些数字集结点从i-1转移到i所减少的贡献，还是用f[pos][sum],只有最后sum>0才加即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int k,num[60];
ll l,r,len,f[60][1200][2];

ll dfs1(int pos,int sum,bool lim)
{
    if(pos>len)return sum;
    if(f[pos][sum][lim]!=-1)return f[pos][sum][lim];
    ll res=0;int end=(lim?num[pos]:k-1);
    for(int i=0;i<=end;i++)
        res+=dfs1(pos+1,sum+i*(pos-1),lim&&(i==end));
    return f[pos][sum][lim]=res;
}

ll dfs2(int pos,int sum,int m,bool lim)
{
    if(pos>len)return max(sum,0);
    if(f[pos][sum][lim]!=-1)return f[pos][sum][lim];
    ll res=0;int end=(lim?num[pos]:k-1);
    for(int i=0;i<=end;i++)
        res+=dfs2(pos+1,sum+(pos<m?-i:i),m,lim&&(i==end));
    return f[pos][sum][lim]=res;
}

ll solve(ll n)
{
    len=0;
    while(n)num[++len]=n%k,n/=k;
    reverse(num+1,num+len+1);
    memset(f,-1,sizeof(f));
    ll res=dfs1(1,0,1); 
    for(int i=2;i<=len;i++)
    {
        memset(f,-1,sizeof(f));
        res-=dfs2(1,0,i,1);
    }
    return res;
}

int main()
{
    //freopen("lx.in","r",stdin);
    scanf("%lld%lld%d",&l,&r,&k);
    cout<<solve(r)-solve(l-1);
    return 0;
}

秒客网