bzoj3598 [Scoi2014]方伯伯的商场之旅

数位dp,我们肯定枚举集合的位置,但是如果每次都重新dp的话会很麻烦,所以我们可以先钦定在最低位集合,dp出代价,然后再一步步找到正确的集合点,每次更改的代价也dp算就好了。

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int L,R,K;
int a[];
int f[][];
int dfs(int pos,int sum,int lim){
if(!pos)return sum;
if(!lim&&f[pos][sum]!=-)return f[pos][sum];
int up=lim?a[pos]:K-;
int ans=;
for(int i=;i<=up;i++)
ans+=dfs(pos-,sum+(pos-)*i,lim&&(i==up));
if(!lim)f[pos][sum]=ans;
return ans;
}
int dfs(int pos,int zd,int sum,int lim){
if(sum<)return ;
if(!pos)return sum;
if(!lim&&f[pos][sum]!=-)return f[pos][sum];
int up=lim?a[pos]:K-;
int ans=;
for(int i=;i<=up;i++){
if(pos>=zd)ans+=dfs(pos-,zd,sum+i,lim&&(i==up));
else ans+=dfs(pos-,zd,sum-i,lim&&(i==up));
}
if(!lim)f[pos][sum]=ans;
return ans;
}
int work(int x){
int pos=;
while(x){
a[++pos]=x%K;
x/=K;
}
memset(f,-,sizeof f);
int ans=dfs(pos,,);
for(int i=;i<=pos;i++){
memset(f,-,sizeof f);
ans-=dfs(pos,i,,);
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&L,&R,&K);
printf("%lld\n",work(R)-work(L-));
return ;
}
上一篇:JAVA经典算法40题面向过程


下一篇:Java经典算法四十例编程详解+程序实例