TJOJ 4148 （数位dp）

题意：问1到n（1<=n<=10^8）所有的数，总共有多少个0出现。

做法：

很明显的数位dp

数位dp的题目我发现都可以用暴搜+记忆话过掉，而且写起来超级方便。赛场上第一个AC这道题。

暴搜是这么写的

#include<cstdio>
#include<cstring>
using namespace std;
char s[100];
int a[100];
int n;
long long get(int pos,bool up,bool zr,int now)
{
	if (pos>n) return now;
	long long ret=0;
	for (int i=0;i<=9;i++)
	{
		if (up&&i>a[pos]) continue;
		bool uup=up;
		if (i<a[pos]) uup=0;
		bool zzr=zr;
		if (i!=0) zzr=0;
		int nnow=now;
		if (i==0&&!zr) nnow++;
		ret+=get(pos+1,uup,zzr,nnow);
	}
	return ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		for (int i=1;i<=n;i++) a[i]=s[i]-'0';
		printf("%lld\n",get(1,1,1,0));
	}
}

加个记忆化复杂度就变成了f数组的复杂度

#include<cstdio>
#include<cstring>
using namespace std;
char s[100];
int a[100];
int n;
long long f[100][2][2][100];
long long get(int pos,bool up,bool zr,int now)
{
	if (pos>n) return now;
	long long ret=f[pos][up][zr][now];
	if (ret!=-1) return ret;
	ret=0;
	for (int i=0;i<=9;i++)
	{
		if (up&&i>a[pos]) continue;
		bool uup=up;
		if (i<a[pos]) uup=0;
		bool zzr=zr;
		if (i!=0) zzr=0;
		int nnow=now;
		if (i==0&&!zr) nnow++;
		ret+=get(pos+1,uup,zzr,nnow);
	}
	return f[pos][up][zr][now]=ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		for (int i=1;i<=n;i++) a[i]=s[i]-'0';
		memset(f,-1,sizeof(f));
		printf("%lld\n",get(1,1,1,0));
	}
}

数位dp的套路就是这样，暴搜加记忆化，超级简单。