B-number
题意:
求1-n(<=1e9)中是13的倍数且包含“13”的个数。多组数据。
数位DP
#include<bits/stdc++.h>
using namespace std;
int n;
int dat[15],cnt;
int f[13][11][2][15];
int dfs(int pos,int pre,bool limit,bool hav,int lj)
{
if(pos==0)return f[pos][pre][hav][lj]=hav&&(lj==0);
if(!limit && f[pos][pre][hav][lj]!=-1)return f[pos][pre][hav][lj];
int up=limit?dat[pos]:9;
int ans=0;
for(int i=0;i<=up;++i)
{
ans+=dfs(pos-1,i,limit&&(i==up),hav||(pre==1&&i==3),(lj*10+i)%13);
}
if(!limit)f[pos][pre][hav][lj]=ans;
return ans;
}
int main()
{
while(scanf("%d",&n)==1)
{
cnt=0;
memset(f,-1,sizeof f);
while(n)
{
++cnt;
dat[cnt]=n%10;
n/=10;
}
printf("%d\n",dfs(cnt,0,1,0,0));
}
return 0;
}
标签:HDU3652,pre,int,lj,number,pos,hav
From: https://www.cnblogs.com/gryzy/p/16753998.html