处女座和小姐姐（三）（数位dp）

处女座和小姐姐（三）（数位dp）

题目描述

经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！ 处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。 现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。

输入描述:

一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数，表示处女座内心激动的次数。

示例1

输入

10 20

输出

1

备注:

0≤l≤r≤10^18

思路：

和不要49，不要62差不多。

直接上数位dp模板。

代码：

#include #include #include using namespace std;int a[30];long long dp[30][20][15];long long sove(int pos,int pre,int bb,int limit){ if(pos==-1)return bb; if(!limit&&dp[pos][pre][bb]!=-1)return dp[pos][pre][bb]; long long sum=0; int end=limit?a[pos]:9; for(int i=0;i<=end;i++) { if(i==6)sum+=sove(pos-1,i,1,limit&&(i==a[pos])); else sum+=sove(pos-1,i,bb,limit&&(i==a[pos])); } if(!limit)dp[pos][pre][bb]=sum; return sum;}long long go(long long x){ int pos=0; while(x) { a[pos++]=x%10; x/=10; } return sove(pos-1,0,0,1);}int main(){ long long m,n; memset(dp,-1,sizeof(dp)); scanf("%lld%lld",&n,&m); printf("%lld\n",go(m)-go(n-1)); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。