专题七 动态规划

题解动态规划

[题目][A]

数位dp

题目大意：

输出[n,m]区间中的吉利数字的个数。(0 < n <= m < 1000000)吉利数字是数字钟不含4和62的数。当n,m均为0时，输入结束。

解题思路：

数位dp。[n,m]的范围可以由(0,m+1)-(0,n)得到，即求这两个范围里的吉利数然后相减。
统一的做法来求(0,n)范围内的吉利数，用dp[i][j]来表示以j开头的i位数，有多个，这些j开头的i位数为吉利数有多少个。
dp[i][j]的意义下，我们可以处理到每位数，当符合要求时，dp[i][j] += dp[i-1][k]，(k为i-1位数的开头的数)。
然后将n,m分别输入处理，把每一位数分解出来，通过小于对应位数的该位的数的列举，然后把符合条件的以j开头的i位数的dp[i][j]加起来，就是答案。如果某位数处理完后，发现该位及其前缀已经不符合条件，那么后面再进行下去，也没有意义。(数位处理的要点，处理以j开头的i位数，超出i位数的保持原数据不变，只处理这i位数)
时间复杂度O(1),空间复杂度O(1).

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[10][10];
void init()
{
    int i,j,k;
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for(i = 1;i <= 7;i++)
    {
        for(j = 0;j <= 9;j++)
        {
            for(k = 0;k <= 9;k++)
            {
                if(j != 4 && !(j == 6 && k == 2))
                {
                    dp[i][j] += dp[i-1][k];
                }
            }
        }
    }
}
int solve(int n)
{
    int num[10];
    int len = 0;
    int i,j;
    int ans = 0;
    init();
    while(n > 0)
    {
        num[++len] = n%10;
        n /= 10;
    }
    num[len+1] = 0;
    for(i = len;i >= 1;i--)
    {
        for(j = 0;j < num[i];j++)
        {
            if(j != 4 && !(num[i+1] == 6 && j == 2))
                ans += dp[i][j];
        }
        if(num[i] == 4 || (num[i] == 2 && num[i+1] == 6))
            break;
    }
    return ans;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF && !(n == 0 && m == 0))
    {
        printf("%d\n",solve(m+1) - solve(n));
    }
    return 0;
}