A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13 100 200 1000
Sample Output
1 1 2 2
与其叫数位dp,我觉得这种题其实就是搜索
此题我开了4维数组
分别记录当前位数,是否被限制,前面是否为1,前面是否出现了13
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[20][20][2][2],a[20];
int dfs(int pos,int mod,int lim,int sta,int bef)
{
int s,ans=0;
if(pos==0) return mod%13==0&&sta==1;
if(!lim&&dp[pos][mod][bef][sta]!=-1) return dp[pos][mod][bef][sta];
s=lim==1?a[pos]:9;
int temp;
for(int i=0; i<=s; i++)
{
temp=(mod*10+i)%13;
//cout<<pos<<" "<<lim<<" "<<bef<<" "<<"temp="<<temp<<" "<<s<<" "<<i<<endl;
if(i==1)
{
ans+=dfs(pos-1,temp,lim&&i==s,sta,1);
}
else if(bef&&i==3)
{
ans+=dfs(pos-1,temp,lim&&i==s,1,0);
}
else
{
ans+=dfs(pos-1,temp,lim&&i==s,sta,0);
}
}
if(!lim) dp[pos][mod][bef][sta]=ans;
//cout<<ans<<" "<<pos<<" "<<bef<<endl;
return ans;
}
int solve(int x)
{
int cnt=0;
while(x!=0)
{
cnt++;
a[cnt]=x%10;
x/=10;
}
return dfs(cnt,0,1,0,0);
}
int main()
{
int n;
memset(dp,-1,sizeof(dp));
while(~scanf("%d",&n))
{
cout<<solve(n)<<endl;
//printf("%d
",ans);
}
return 0;
}