HDU 2089 不要62：数位dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意：

　　问你在区间[n,m]中，有多少个数字不含"4"且不含"62"。

题解：

　　表示状态：

　　　　dp[i][j] = numbers

　　　　数字有i位，开头为数字j，合法的数字个数。

　　如何转移：

　　　　dp[i][j] = ∑ dp[i-1][k]　　(j!=4,6 && k!=4)

　　　　dp[i][6] = ∑ dp[i-1][k]　　(k!=2,4)

　　　　dp[i][4] = 0

　　边界条件：

　　　　dp[0][0] = 1

　　找出答案：

　　　　题目中询问的是区间，所以答案可以用差分形式表示：

　　　　　　ans = cal_ans(m+1) - cal_ans(n)

　　　　　　cal_ans(i)表示小于i的合法数字个数。

　　　　比如我要求小于32768的合法数字个数：

　　　　　　ans += 0xxxx, 1xxxx, 2xxxx的个数

　　　　　　ans += 30xxx, 31xxx的个数

　　　　　　ans += 320xx, 321xx, 322xx, 323xx, 324xx, 325xx, 326xx的个数

　　　　　　ans += 3270x, 3271x, 3272x, 3273x, 3274x, 3275x的个数

　　　　　　ans += 32760, 32761, 32762, 32763, 32764, 32765, 32766, 32767的个数（均为1）

　　　　所以依次枚举i（从len到1），意思是i+1位之前的数字都已确定，该枚举第i位了。

　　　　枚举第i位的数字为j。ans+=dp[i][j]的条件是前一位和当前位不能构成"62"，即：d[i+1]!=6 || j!=2

　　　　并且，一旦(d[i]==4 || (d[i+1]==6 && d[i]==2))，就应退出循环，因为之后枚举的数字一定都是不合法的。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_L 10

 #define MAX_D 15

 using namespace std;

 int n,m;

 int d[MAX_L];

 int dp[MAX_L][MAX_D];

 void cal_dp()

 {

     memset(dp,,sizeof(dp));

     dp[][]=;

     for(int i=;i<=;i++)

     {

         for(int j=;j<=;j++)

         {

             for(int k=;k<=;k++)

             {

                 if(j!= && (j!= || k!=))

                 {

                     dp[i][j]+=dp[i-][k];

                 }

             }

         }

     }

 }

 int cal_ans(int x)

 {

     int len=;

     int ans=;

     while(x)

     {

         d[++len]=x%;

         x/=;

     }

     d[len+]=;

     for(int i=len;i>;i--)

     {

         for(int j=;j<d[i];j++)

         {

             if(d[i+]!= || j!=) ans+=dp[i][j];

         }

         if(d[i]== || (d[i+]== && d[i]==)) break;

     }

     return ans;

 }

 int main()

 {

     cal_dp();

     while(cin>>n>>m)

     {

         if(n== && m==) break;

         cout<<cal_ans(m+)-cal_ans(n)<<endl;

     }

 }

巴特西

HDU 2089 不要62：数位dp

最新文章

热门文章