P2657 [SCOI2009]windy数


code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15];
int a[15],len;
ll dfs(int pos,int pre,int lead,int limit)
{
	if(pos>len) return 1;
	if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];
	int up=limit?a[len-pos+1]:9;
	ll ans=0;
	for(int i=0;i<=up;i++) {
		if(abs(i-pre)<2) continue;
		if(lead&&i==0) ans+=dfs(pos+1,-2,1,limit&&i==up);
		else ans+=dfs(pos+1,i,0,limit&&i==up);	
	}
	return (!limit&&!lead)?(dp[pos][pre]=ans):ans;
}
ll cal(ll x)
{
	len=0;
	memset(dp,-1,sizeof(dp));
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	return dfs(1,-2,1,1);
}
int main()
{
	ll l,r;
	cin>>l>>r;
	cout<<cal(r)-cal(l-1);
	return 0;
}

P2602 [ZJOI2010]数字计数


code ： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15];
int a[15],len;
ll dfs(int pos,ll cnt,int dig,int lead,int limit)
{
	if(pos>len) return cnt;
	if(!lead&&!limit&&dp[pos][cnt]!=-1) return dp[pos][cnt];
	int up=limit?a[len-pos+1]:9;
	ll ans=0;
	for(int i=0;i<=up;i++) ans+=dfs(pos+1,cnt+((i||lead==0)&&i==dig),dig,!i&&lead,limit&&i==up);
	return (!limit&&!lead)?(dp[pos][cnt]=ans):ans;
}
ll cal(ll x,int i)
{
	len=0;
	memset(dp,-1,sizeof(dp));
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	return dfs(1,(ll)0,i,1,1);
}
int main()
{
	ll l,r;
	cin>>l>>r;
	for(int i=0;i<=9;i++) cout<<cal(r,i)-cal(l-1,i)<<" ";
	return 0;
}