HDU2089-不要62-同样DP方程一种AC一种WA+趁热打铁

（有任何问题欢迎留言或私聊

点击进入题目：

中文题面，意思大概就是求出区间[N,M]内的吉利数个数，吉利数就是不含4和62的数字。

思路：

考虑状态的表示方法：  dp[i[[0]表示前 i 位数，吉利数的个数  dp[i][1]表示前 i 位数，首位为2的吉利数的个数  dp[i][2]表示前 i 位数，不吉利的的个数

状态转移方程

由此可得出状态转移方程，同时预处理出所有状态：

 dp[i][0] = dp[i-1][0]*9-dp[i-1][1];//在i-1位且为吉利数的前面补上除了4以外的9位数；减去补了6后出现62的情况  dp[i][1] = dp[-1][0];//因为dp[i][1]还是吉利数的个数，只是开头为2而已；所以直接高位补2，数量等于dp[i-1][0]  dp[i][2] = dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];//dp[i-1][2]本来就不是吉利数，高位补上任意10个数字；dp[i-1][1]前面补上6；dp[i-1][0]前面补上4

初始化：

dp[0][0] = 1 0位数确实不是不吉利的数字，这也是一种方案，所以赋值为1。 代码中还有一些解释：

AC代码：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int dp[10][3]={0}; int get2(int x){//求出小于x的吉利数个数 int num[15]={0}; int sum=x,k=0,unLucky=0; while(x){//把x每一位取出来 num[++k]=x%10; x/=10; } num[k+1]=0; bool isUnlucky=false;//从高位到低位枚举，确定此数是不吉利数后，变为true for(int i=k;i>=1;--i){//累加不吉利的数的数量 unLucky+=dp[i-1][2]*num[i]; if(isUnlucky){//从上一位开始确定了unLucky后， unLucky+=dp[i-1][0]*num[i]; }else{ if(num[i]>4){ unLucky+=dp[i-1][0];//dp[i-1][0]等于dp[i][1],怎么加都行 } if(num[i+1]>6){ unLucky+=dp[i][1]; } if(num[i+1]==6&&num[i]>2){ unLucky+=dp[i-1][0]; } } if(num[i]==4||(num[i+1]==6&&num[i]==2)){//在第i位确定了是unLucky isUnlucky=true; } } return sum-unLucky; } int main(int argc, char const *argv[]) { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=8;++i){ dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]*10; } int n,m; while(~scanf("%d%d",&n,&m)&&(n+m)){ printf("%d\n",get2(m+1)-get2(n)); //get2(i)得到的是区间[1,i)不吉利数的个数 } return 0; }

WA代码：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int dp[10][3]={0}; int get1(int x){//求出小于等于x的吉利数的个数 int num[15]={0}; int sum=x,k=0,unLucky=0; while(x){ num[++k]=x%10; x/=10; } num[k+1]=0; bool isUnlucky=false;//从高位到低位枚举，确定此数是不吉利数后，变为true for(int i=k;i>=1;--i){//累加不吉利的数的数量 unLucky+=dp[i-1][2]*num[i]; if(isUnlucky){ unLucky+=dp[i-1][0]*num[i]; }else{ if(num[i]>4){ unLucky+=dp[i-1][0]; } if(num[i]==4&&i==1){ unLucky+=dp[i-1][0]; } if(num[i+1]>6&&num[i]>=2){ unLucky+=dp[i][1]; } if(num[i+1]==6&&num[i]>=2){ if(num[i]==2){ if(i==1)unLucky+=dp[i-1][0]; }else{ unLucky+=dp[i-1][0]; } } } if(num[i]==4||(num[i+1]==6&&num[i]==2)){ isUnlucky=true; } } return sum-unLucky; } int main(int argc, char const *argv[]) { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=8;++i){ dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]*10; } int n,m; while(~scanf("%d%d",&n,&m)&&(n+m)){ printf("%d\n",get1(m)-get1(n-1)); //get2(i)得到的是区间[1,i]不吉利数的个数 } return 0; }

趁热打铁：

突然想起了上周湘潭邀请赛热身赛的D题，好像也可用这种数位dp的方法解决，题目是3的倍数，我只记得大概：

给你一个很长的数字，比如42103，你可以删除一些数字，问你有多少种删除的方法，是的删除后的数字是3的倍数？数字不能有前导0（我有一点记不清楚了，就是如果这个数字本来就是3的倍数，不删的话是不是一种方案）

具体题目不记得了，但还是可写，反正问题核心思想是一致的。

思路：

类比上题，用dp[i][j]表示一个数从后往前数，前 i 位中所有位数和是 j 的方案数： j %=3，所以j的取值为0，1，2：

dp[i][0]表示前 i 位中位数和位0的方案数 dp[i][1]表示前 i 位中位数和位1的方案数 dp[i][2]表示前 i 位中位数和位2的方案数

为什么只考虑位数和mod3之后的方案数呢？

因为一个数能不能被3整除，只和你所有位数之和是不是等于3有关。 位数和mod3之后只有三种可能0，1，2；在此基础上数位dp即可

栗子：42103

这里先不考虑前导的问题，到最后会统一处理 dp[3][0]表示从后往前数前3位中，位数和位0的方案数  dp[3][0]=3,具体三种为：3，0，03。说了这里先不考虑前导0的影响，所以3和03算两种情况  dp[3][1]=4,具体为：13，10，103，1  dp[3][2]=0

状态转移方程：

由此不难得出状态转移方程： if(v[i]==0): //当前位的数字mod3等于0  dp[i][0]=dp[i+1][0]*2+1;//当前位mod3等于0，取不取当前位对mod后的数值无影响，这是乘2的原因；当前位单独也可做一个case，所以加一。详情看代码解释  *dp[i][1]=dp[i+1][1]2;  *dp[i][2]=dp[i+1][2]2;

if(v[i]==1): //当前位的数字mod3等于1  dp[i][0]=dp[i+1][0]+dp[i+1][2];  dp[i][1]=dp[i+1][1]+dp[i+1][0]+1;  dp[i][2]=dp[i+1][2]+dp[i+1][1]; if(v[i]==2): //当前位的数字mod3等于2  dp[i][0]=dp[i+1][0]+dp[i+1][1];  dp[i][1]=dp[i+1][1]+dp[i+1][2];  dp[i][2]=dp[i+1][2]+dp[i+1][0]+1;

虽然我觉得这个状态转移方程非常好理解，浅显易懂，很容易想到，但我觉得还是解释一下比较好，不懂的同学可以留言或私信问我，详情看下面的代码：

初始化：

memset(dp,0,sizeof(dp));

代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 10005; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int n; int dp[N][3]; char ar[N]; int v[N]; int main(){ while(~scanf("%s",ar+1)){ int len = strlen(ar+1); dp[len+1][0]=dp[len+1][1]=dp[len+1][2]=0;//初始化 //printf("*%d\n",len ); for(int i=1;i<=len;++i){ v[i]=(ar[i]-'0')%3;//处理出v数组 //printf("*%d %c\n",v[i],ar[i] ); } for(int i=len;i>=1;--i){ if(v[i]==0){ dp[i][0]=dp[i+1][0]*2+1; //当前位mod3等于0，所以你可用当前位和后面mod3等于0的方案相结合，这样的结果mod3还是等于0，方案数:dp[i+1][0]；也可以不要当前位,方案数:dp[i+1][0]；也可以当前位单独做一个情况，方案数：1。和为dp[i+1][0]*2+1 dp[i][1]=dp[i+1][1]*2; //当前位mod3等于0，选不选用当前位，对mod3之后的数值无影响，所以方案数:dp[i+1[1]*2，后面同理 dp[i][2]=dp[i+1][2]*2; //解释了上面这两个，剩下的以此类推就很简单了，不多赘述，不懂的同学可以留言或私信问我 }else if(v[i]==1){ dp[i][0]=dp[i+1][0]+dp[i+1][2]; dp[i][1]=dp[i+1][1]+dp[i+1][0]+1; dp[i][2]=dp[i+1][2]+dp[i+1][1]; }else if(v[i]==2){ dp[i][0]=dp[i+1][0]+dp[i+1][1]; dp[i][1]=dp[i+1][1]+dp[i+1][2]; dp[i][2]=dp[i+1][2]+dp[i+1][0]+1; } } int ans=dp[1][0]; for(int i=1;i<=len;++i){ if(ar[i]=='0'){//消除前导0的影响，如果你懂了状态转移方程，这里应该就懂了 ans-=(dp[i+1][0]+1); } } printf("%d\n",ans ); } return 0; }