数位DP

数位DP：

以前遇到数位dp的题都是用其他的方法做的，这些遇到标准的数位dp的题就傻眼了。之前一道题计算1,2的个数，差点摸到数位dp的门槛了。

#include <cstdio>
#include <memory.h>

int dp[8][3];
//d[l][0]表示不存在不吉利数字 (包含d[l][1])
//d[l][1]表示不存在不吉利数字，但首位是2 
//d[l][2]表示存在不吉利的数字

void init() {
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 1; i <= 7; ++i) {
        dp[i][0] = 9 * dp[i - 1][0] - dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
        //前面加4 ，或者 dp[i - 1][1]前面加6 
        dp[i][2] = 10 * dp[i - 1][2] + dp[i - 1][0] + dp[i - 1][1];
    } 
}

int sum(int t) {//统计0到t的不吉利的数的个数 
    int len = 0;
    int all = t;
    int digit[8] = {0}; 
    while (t) {
        digit[++len] = t % 10;
        t /= 10;
    }
    int ans = 0; //不吉利的数的个数 
    bool flag = false; //是否已成为不吉利的号 
    int last = 0;
    for (int i = len; i >= 0; --i) {
        ans += dp[i - 1][2] * digit[i];
        if (flag) ans += dp[i - 1][0] * digit[i];
        if (!flag && digit[i] > 4) //当前位可以为4 
            ans += dp[i - 1][0];
        if (!flag && digit[i] > 6) //当前位可以为2,4,6
             ans += dp[i - 1][1]; //为6,则把前一位的2算上
        if (!flag && last == 6 && digit[i] > 2) //若上一位已经为6，当前位为2 
            ans += dp[i - 1][0]; 
        if(digit[i] == 4 || (last == 6 && digit[i] == 2))
            flag = true;
        last = digit[i];
    }
    return all - ans;
} 
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, m;
    init();
    while (scanf("%d%d", &n, &m) != EOF && (n != 0 || m != 0)) {
        printf("%d
", sum(m + 1) - sum(n));
    } 
    return 0;
}

View Code

题目：有趣的数

问题描述

我们把一个数称为有趣的，当且仅当：

1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。

2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。

3. 最高位数字不为0。

因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。

请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

输入格式

输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。

输出格式

输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

样例输入

样例输出

答案用的数位dp和记忆化搜索

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <deque>
#include <list>
 
using namespace std;
 
long long f[2000][3][2]; // f[seq_k to place][0: to place 0 , 1: ethier 0 or 1, 2 : must be 1][3 is placed ? 1 : 0]
 
int dp(int n, int p1, int p3)
{
         long long &now = f[n][p1][p3];
         if (now != -1)
                   return now;
         if (n == 0)
         {
                   if (p1 == 2 && p3 == 1)
                   {
                            now = 1;
                   }else
                   {
                            now = 0;
                   }
                   return now;
         }
         now = 0;
         if (p1 == 0)
         {
                   now += dp(n-1, 1, p3); // go 0
         }else if (p1 == 1)
         {
                   now += dp(n-1, 1, p3); // go 0
                   now += dp(n-1, 2, p3); // go 1
         }else // p1 == 2
         {
                   now += dp(n-1, 2, p3); // go 1
         }
         
         if (p3 == 0)
         {
                   now += dp(n-1, p1, p3); // go 2;
                   now += dp(n-1, p1, 1); // go 3;
         }else
         {
                   now += dp(n-1, p1, 1); // go 3;
         }
         now %= 1000000007;
}
 
int main()
{
         int n;
         cin >> n;
         memset(f, -1, sizeof(f));
         int ans = dp(n - 1, 0, 0); // seq[n] is 2
         cout << ans << endl;
         return 0;
}

View Code