数位dp的思路一定要清晰!!
- 想个办法初始化f数组
- 在dp时一定要保留last信息,本题中的last为之前遍历过的数位中,=p的个数
- 每次遍历,res要加上之前last中的p的个数,
res+=x*last*pow(10,i)
如遍历到3345,要求求3的个数,遍历到4时,i=1,3300到3339,每一个数都要加上前两位的3个个数,
一共加了2x4x10个3
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int N=12;
//f[i][j][k] 首位为k的j位数,数字i出现的次数
int f[10][N][N];
int dp(int n,int p)
{
int res=0;
int last=0;
vector<int> num;
int tmp_n=n;
while(n)
{
num.push_back(n%10);
n=n/10;
}
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
if(i==num.size()-1)
{
for(int j=1;j<x;j++)
{
res+=f[p][i+1][j];
}
}
else
{
for(int j=0;j<x;j++)
{
res+=f[p][i+1][j];
}
}
//last用于保留之前遍历过的位数中所包含的p,每次往后推一位都要加上之前的
res+=x*last*pow(10,i);//算上前面的p的个数
if(x==p) last++;//记录last
if(!i) res+=last;//这个数本身所含有的
}
//cout<<"res1="<<res<<endl;
for(int i=1;i<num.size();i++)
{
for(int j=1;j<=9;j++)
res+=f[p][i][j];
}
return res;
}
int main()
{
for(int i=0;i<=9;i++)
{
f[i][1][i]=1;
}
for(int i=0;i<=9;i++)
{
for(int j=2;j<=N-1;j++)
{
for(int k=0;k<=9;k++)
{
if(k==i) f[i][j][k]=f[i][j][k]+pow(10,j-1);
for(int q=0;q<=9;q++)
{
f[i][j][k]+=f[i][j-1][q];
}
}
}
}
//cout<<f[0][2][2]<<endl;
//cout<<dp(30,0);
int a,b;
while(cin>>a>>b,a||b)
{
if(a>b)
{
int t=a;
a=b;
b=t;
}
for(int i=0;i<=9;i++)
{
cout<<dp(b,i)-dp(a-1,i)<<" ";
}
cout<<endl;
}
return 0;
}
请教一下这个预处理的定义为什么模拟起来不太对? 按照定义f[i][j][k] 首位为k的j位数,数字i出现的次数
比如f[1][2][2] : 表示 最高位是1 的两位数 的2出现的次数.
按照这个定义 数字2 和 12 符合条件 应该是2 但是把f[][][]打出来 发现f[1][2][2] = 1 ?
还是说f[][][]的j位数 是指恰好是j位 而数字2是1位数 而不是两位 所以没算数字2 只算了数字12, 所以是1个 ?
谢谢大佬!
f[i][j][k] 表示首位为k的j位数,数字i出现的次数。
你所说的f[1][2][2] 表示的是以2为首位的2位数,数字1出现的次数,所有以2为首的两位数有:20,21,22,23,24,25,26,27,28,29. 只有21出现了一次1. 因此f[1][2[2]=1.
这里的定义你再想想,发现你说的好像都不对。。还有j位数的意思是恰好是j位数,具体例子看我刚刚所说的f[1][2][2]
你的对! 谢谢大佬!! 我晕了已经:( 数字dp想递推关系真的是太难了!