fzu 2113 Jason的特殊爱好 --- 数位dp

本文主要是介绍fzu 2113 Jason的特殊爱好 --- 数位dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题目名字起的真龊。。。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;ll dp[30][20],a,b,num[30];ll dfs(ll n,ll pos,bool flag)
{if(pos==-1) return n;if(!flag&&dp[pos][n]!=-1) return dp[pos][n];ll ans=0,p;if(flag) p=num[pos];else p=9;for(ll i=0;i<=p;i++){if(i==1) ans+=dfs(n+1,pos-1,flag&&i==p);//这里写成了num[i] 一直错 终于理解了这个dfselse ans+=dfs(n,pos-1,flag&&i==p);}if(!flag) dp[pos][n]=ans;return ans;
}ll cal(ll x)
{ll l=0;while(x){num[l++]=x%10;x/=10;}return dfs(0,l-1,1);
}int main()
{memset(dp,-1,sizeof dp);while(~scanf("%I64d%I64d",&a,&b)){if(a>b) swap(a,b);printf("%I64d\n",cal(b)-cal(a-1));}return 0;
}

这篇关于fzu 2113 Jason的特殊爱好 --- 数位dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---