HDU 3652 & HDU 4734 数位DP 记忆化搜索

数位dp中最重要的是要保证每一个dp能够唯一的表示状态。

HDU 3652

B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6311    Accepted Submission(s): 3648

Problem Description

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.

Input

Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).

Output

Print each answer in a single line.

Sample Input

13 100 200 1000

Sample Output

1 1 2 2

Author

wqb0039

和昨天的题目类似，但是多加了一个判断条件，对13取模位0。这个只需要知道一个模运算的性质（a * b）mod n = (a mod n) * (b mod n) mod n。在10进制，对一个大数取模，只需要从高位到低位依次取模的值乘以10加上当前位取模即可。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int a[15];
int dp[15][15][3];

int dfs(int pre, int pos, int mod, int status, bool limit)
{
    if(pos == 0) return status == 2 && mod == 0;
    if(!limit && dp[pos][mod][status] != -1) return dp[pos][mod][status];
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for(int i = 0; i <= up; i++)
    {
        int nstatus;
        int nmod = (mod * 10 + i) % 13;
        if(status == 2 || pre == 1 && i == 3)
            nstatus = 2;
        else if(i == 1)
            nstatus = 1;
        else
            nstatus = 0;
        ans += dfs(i, pos-1, nmod, nstatus, limit && i == up);
    }
    if(!limit) dp[pos][mod][status] = ans;
    return ans;
}

int solve(int x)
{
    int len = 0;
    while(x)
    {
        a[++len] = x%10;
        x /= 10;
    }
    a[len + 1] = 0;
    return dfs(-1, len, 0, 0, true);
}

int main()
{
    int n;
    memset(dp, -1, sizeof(dp));
    while(scanf("%d", &n) == 1)
    {
        printf("%d
", solve(n));
    }
    return 0;
}

HDU 4734

F(x)

Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5568    Accepted Submission(s): 2087

Problem Description

For a decimal number x with n digits (A_nA_n-1A_n-2 ... A₂A₁), we define its weight as F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 10⁹)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

3 0 100 1 10 5 100

Sample Output

Case #1: 1 Case #2: 2 Case #3: 13

Source

2013 ACM/ICPC Asia Regional Chengdu Online

dp选取的状态表示方法一定要是对于每个样例都没有影响的。

先贴上AC代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int a[15];
int dp[15][200000];

int dfs(int pos, int status, bool limit)
{
    if(pos == 0) return status >= 0;
    if(status < 0) return 0;
    if(!limit && dp[pos][status] != -1) return dp[pos][status];
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for(int i = 0; i <= up; i++)
    {
        ans += dfs(pos-1, status - i * (1 << (pos-1)), limit && up == i);
    }
    if(!limit) dp[pos][status] = ans;
    return ans;
}

int solve(int y, int x)
{
    int k = 1;
    int weight = 0;
    while(y)
    {
        weight += (y%10) * (k);
        k *= 2;
        y /= 10;
    }
    int len = 0;
    while(x)
    {
        a[++len] = x%10;
        x /= 10;
    }
    a[len + 1] = 0;
    return dfs(len, weight, true);
}

int main()
{
    int a, b, kase = 0, Q;
    scanf("%d", &Q);
    memset(dp, -1, sizeof(dp));
    while(Q--)
    {
        scanf("%d%d", &a, &b);
        printf("Case #%d: %d
", ++kase, solve(a,b));
    }
    return 0;
}

然后在贴上开始超时的代码，反思得到的经验就是，对于数位DP描述的选择，应该是对于问题的变化参数没有影响的。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int a[15];
int dp[15][1 << 15];
int weight;

int dfs(int pos, int status, bool limit)
{
    if(pos == 0) return status <= weight;
    if(!limit && dp[pos][status] != -1) return dp[pos][status];
    int up = limit ? a[pos] : 9;
    int ans = 0;
    for(int i = 0; i <= up; i++)
    {
        if(status + i * (1 << (pos-1)) > weight) continue;
        ans += dfs(pos-1, status + i * (1 << (pos-1)), limit && up == i);
    }
    if(!limit) dp[pos][status] = ans;
    return ans;
}

int solve(int y, int x)
{
    int k = 0;
    memset(dp, -1, sizeof(dp));
    weight = 0;
    while(y)
    {
        weight += (y%10) * (1 << k);
        k++;
        y /= 10;
    }
    int len = 0;
    while(x)
    {
        a[++len] = x%10;
        x /= 10;
    }
    a[len + 1] = 0;

    return dfs(len, 0, true);
}

int main()
{
    int a, b, kase = 0, Q;
    scanf("%d", &Q);
    while(Q--)
    {
        scanf("%d%d", &a, &b);
        printf("Case #%d: %d
", ++kase, solve(a,b));
    }
    return 0;
}