方伯伯的商场之旅
输入格式：
输入仅有1 行，包含3 个用空格分隔的整数L，R，K，表示商场给方伯伯的2 个整数，以及进制数输出格式：
输出仅有1 行，包含1 个整数，表示最少的代价。样例输入：
3 8 3
样例输出：
5
数据范围：
时间限制：
3s空间限制：
64M具体思路:数位DP
先假装所有数都转移到第一位上,
然后扫一下其他位,把对答案有益的加上
AC代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r,k,dp[100][10000],num[100],top=0,t[10000];
int DFS(int pos,int sum,int lim)
{
if(pos==top+1)return sum;
if(!lim&&~dp[pos][sum])return dp[pos][sum];
int res=0,mx=lim?num[pos]:k-1;
for(int i=0;i<=mx;i++)
res+=DFS(pos+1,sum+i*(pos-1),lim&&i==mx);
return lim?res:dp[pos][sum]=res;
}
int dfs(int pos,int sum,int lim,int mid)
{
if(pos==top+1)return max(sum,0ll);
if(!lim&&~dp[pos][sum])return dp[pos][sum];
int res=0,mx=lim?num[pos]:k-1;
for(int i=0;i<=mx;i++)
res+=dfs(pos+1,sum+((pos<mid)?-i:i),lim&&i==mx,mid);
return lim?res:dp[pos][sum]=res;
}
int solve(int x)
{
top=0;while(x)top++,num[top]=x%k,x=x/k;
for(int i=1;i<=top/2;i++)swap(num[i],num[top-i+1]);
memset(dp,-1,sizeof(dp));
int ans=DFS(1,0,1);
for(int i=2;i<=top;i++)
{
memset(dp,-1,sizeof(dp));
ans-=dfs(1,0,1,i);
}
return ans;
}
signed main()
{
cin>>l>>r>>k;
printf("%lld
",solve(r)-solve(l-1));
return 0;
}