已经详细注释了,有疑问可以提出来交流。对dfs的参数不太了解的可以百度看看。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=35;
int f[N][N],pos=0,a[N],x,y,k,b;//f[i][j]表示 当前枚举到第i位,前面已经取了j个1的方案数
int dfs(int pos,int pre,int last,int limit)
//pos当前枚举的位数,pre前面取了多少个1,last上一个数是几,limit当前位取数有没有限制
{
if(!pos)return pre==k;//枚举完成了,判断边界这个数是否符合要求
if(last>1)return 0;//如果前一位取了比1大的数,直接不符合要求。
if(!limit&&f[pos][pre]!=-1)return f[pos][pre];//记忆化
int up=limit?a[pos]:b;
int res=0;
if(up==0)res+=dfs(pos-1,pre,0,1);//当前位最高只能取0,直接进入下一位看
else if(up)//当前位最高可以取>=1
{
res+=dfs(pos-1,pre,0,0);//则当前位取0一定合法
if(up>1)
{
if(pre<k)res+=dfs(pos-1,pre+1,1,0);//当前位取1的话
}
else if(up==1)//当前位最高只能取1,那么只能取1了。(取0在前面已经写了)
{
if(pre<k)res+=dfs(pos-1,pre+1,1,1);
}
}
if(!limit)f[pos][pre]=res;
return res;
}
int dp(int n)
{
if(!n)return 0;
int pos=0;
while(n)
{
a[++pos]=n%b;
n/=b;
}
return dfs(pos,0,0,1);
}
int main()
{
memset(f,-1,sizeof f);
cin>>x>>y>>k>>b;
cout<<dp(y)-dp(x-1);
return 0;
}
经评论区大佬提醒,发现可以直接省掉last这个参数,只要保证每次搜索的位都是0-1之间就可以了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=35;
int f[N][N],pos=0,a[N],x,y,k,b;//f[i][j]表示 当前枚举到第i位,前面已经取了j个1的方案数
int dfs(int pos,int pre,int limit)
//pos当前枚举的位数,pre前面取了多少个1,limit当前位取数有没有限制
{
if(!pos)return pre==k;//枚举完成了,判断边界这个数是否符合要求
if(!limit&&f[pos][pre]!=-1)return f[pos][pre];//记忆化
int up = limit? a[pos] : b-1;
int res = 0;
for(int k = 0; k <= min(up,1); k++){当前位最高只能取到1
res += dfs(pos-1,pre +(k==1),limit && k == up );// 状态转移
}
if(!limit)f[pos][pre]=res;
return res;
}
int dp(int n)
{
if(!n)return 0;
int pos=0;
while(n)
{
a[++pos]=n%b;
n/=b;
}
return dfs(pos,0,1);
}
int main()
{
memset(f,-1,sizeof f);
cin>>x>>y>>k>>b;
cout<<dp(y)-dp(x-1);
return 0;
}
巨巨,怎么判断数位DP中状态表示f[i][j]是正确的、不重不漏的?有些题自己写的状态定义和别人的不太一样,wa了。。
一般第一维都是前i位,然后后面的维存的是前i位的某些信息
而且显然如果pre>k的话直接跳出吧,再往后面搜就没意义了,在后面加一行这个,时间缩短一半
res += dfs(pos-1,pre +(k==1),limit && k == up );// 状态转移
能不能详细解释一下啊,为啥是这么转移?
枚举该位填0还是1是为啥呀?可能不是二进制呢?
如果这位没限制是枚举0~b-1呀
这才是我心中的数位dp%%%
状态转移这样写是不是更简单,已ac
厉害,确实last多余了,3个参数就够
%%%%