本文共 2800 字,大约阅读时间需要 9 分钟。
1 1000 0
80
思路:这是一道数位DP的入门题目。先附上ppt的下载链接,讲得很不错的。链接:
首先是初始化dp数组。dp数组保存的就是以 j 为开头的 i 位数字符合要求的数字有多少个。
void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1;//看题目要求,一般状态下以0为开头的0位数状态为1 for(int i=1;i<=7;i++)//一共最大是7位数 { for(int j=0;j<=9;j++)//从右往左,先模拟第 i 位的取值 { for(int k=0;k<=9;k++)//再摸拟第 i-1 位的取值 { if(j!=4&&!(j==6&&k==2))//判断是否符合条件描述 { dp[i][j]+=dp[i-1][k];//如果满足条件相当于第 i 位(取值为j)共 i 位数的状态上加上第 i-1 位(取值为k)共 i-1 位的状态 } } } }}然后计算出来digit数组的值,把数倒序保存在数组中
int cntlen(int n){ int len=0; while(n) { len++; n/=10; } return len;}void cal(int n, int len){ memset(digit,0,sizeof(digit)); for(int i=1;i<=len;i++) { digit[i]=n%10; n/=10; }}最后是如何解决问题的函数
int slove(int n)//其实计算的是【0,n-1】的状态数,这一点PPT中讲到过。对于一个小于n的数,肯定是从高位到低位出现某一位=1;i--)//因为数组是倒序保存的,相当于从原来数的个位开始,直到最高位 { for(int j=0;j
第一:为什么上面代码中的 j 取值必须小于digit[i]?
因为开始表述的性质,我们知道一段区间内符合要求的数是不会等于它本身的。
举例:给出一个数字:123624
先是最高位1的取值,它可以取0。然后开始计算他的状态。他的最大值是0,然后假设后面位置都最大可以取9,得到的数字就是099999。这个数字是小于100000的。
然后跳到下一位2的时候,最高位固定为1不变,就不再需要考虑。接着再考虑下一位。
实际上可以把数字进行拆分:123624=100000+20000+3000+600+20+4
100000之内计算的是【100000,199999】区间的状态
20000之内计算的是 【10000,19999】区间的状态
3000之内计算的是 【1000,2999】区间的状态
600之内计算的是 【100,599】区间的状态
20之内计算的是 【10,19】区间的状态
4之内计算的是 【0,3】区间的状态
前面每一位少的都会在下一位补充进去,但是最后4没有进行补充。合并整个区间就得到的是【0,123623】的状态。
第二:为什么if必须放在后面不放在前面?
因为 j 的取值是小于当前位digit[i]的。
还是上面的例子,123624,倒序放置在数组中就成为了426321。
依照程序从最低位4开始,取值0~3。这个是合法的。但如果把if放在前面,这部分的状态就没有加上去,最终结果就会变小。
当遇到当前位是4或是当前位是2并且下一位是6,就没有必要再进行下去。因为往下走,前面遍历过的位置是不会变的,后面无论怎么变化都是不合规定的。
代码:
#include#include #include #include #include #include using namespace std;int dp[8][10];int digit[10];void init(){ memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=7;i++) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { if(j!=4&&!(j==6&&k==2)) { dp[i][j]+=dp[i-1][k]; } } } }}int cntlen(int n){ int len=0; while(n) { len++; n/=10; } return len;}void cal(int n, int len){ memset(digit,0,sizeof(digit)); for(int i=1;i<=len;i++) { digit[i]=n%10; n/=10; }}int slove(int n){ int sum=0; int len=cntlen(n); cal(n,len); for(int i=len;i>=1;i--) { for(int j=0;j
转载地址:http://avjyz.baihongyu.com/