问题

一般问题的形式为给出一个条件，问一段区间内符合要求的数的个数

举例

HUD-2089 不要62

题意

给出一个区间，求区间内没有连续"62"且没有"4"的数的个数

思路

暴力
直接暴力枚举区间内每一个数来统计
搜索
用深搜的思想实现，比如求0~234之间符合条件的数的个数，可以先枚举第一位，再枚举第二位，再枚举第三位，需要注意的是，当第一位枚举为1时，第二位的范围只能是0~2，同理当前两位为“12”时，第三位只能是0~3
记忆化
观察可以发现，在枚举第一位为1的时候，后两位的枚举其实和第一位为0时一样，都是00~99，所以可以记忆化，节约下大量时间
我们可以设dp[i][j]表示枚举后i位且第i+1位是否为6的答案
以枚举0~2345之间的答案为例

当枚举最高位为1时，后三位的范围为0~999，这一部分的答案在枚举最高位为0的时候已经算过，可以直接累加记忆化的答案进答案，无需继续搜索。

当枚举最高位为2的时候，此时后三位的范围为0~345，无法直接累加，需要继续搜索。

而当前两位为21的时候，此时后两位的范围是0~99，可以直接累加记忆化的答案。

所以我们只需要适当的对前几位枚举结果是否满上限进行标记，并对需要结果进行搜索再记忆化即可

当然也可以记录dp[i][j]表示第 $i$ 位为 $j$ 时的答案，同理

例题

hdu 3702 Balanced Number

题目大意

一个数字被称为 $balanced\quad number$ 当且仅当存位一位 $x$ 使得 $\quad x$ 之前的各位的权值 $\times$ 距离 $x$ 的距离 $\quad$ 等于之后各位的权值 $\times$ 距离
例如 $4139$ ,以 $3$ 为中心，前两位 $41$ 的权值和为 $4\times 2 + 1 \times 1 = 9$ ,同理后一位的权值和为 $9$ ，所以 $4139$ 是一个 $balanced \quad number$

解题思路

假设此时 $a_x$ 是数字 $A$ 的第 $x$ 位，且是一个对称轴

$x$ 之前的所有位权值之和记作 $pre=\sum_{i\gt x}a_i$
之后的所有位权值之和记作 $suf=\sum_{i\lt x}a_i$
假设对称轴向右移动，则两侧权值变为为，左侧 $+(suf+a_x)$ ,右侧 $-pre$ ,显然左侧增大了，右侧减小了，除非两侧变化均为 $0$ ,否则这个位置不会是平衡点，而变化均为 $0$ 则意味着整个数字为 $0$
因此对于任意一个非 $0$ 数字，他的平衡点至多只有一个

我们枚举平衡点，设平衡点之前的数距离平衡点的距离为负数，之后的距离平衡点为正数
设 $dp[len][x][state]$ 表示一个长度为 $len$ 的数字，以第 $x$ 位作为平衡点，权值之和为 $state$

那么 $dp[len][x][state]=\sum_{i=0}^9 dp[len-1][x][state+i\times(len-x)]$
$dp[len][x]相比于dp[len-1][x]$ 相当于在左侧怎加了一位，权值减少了 $i\times (len-x)$ 想要抵消这一位带来的影响，意味着 $len-1$ 位的权值和为 $state+i\times(len-x)$ ，这样两者权值相加即为 $state$

以上是记忆化的部分，最终答案就是枚举每一个平衡点，权值和为 $0$ 的答案,因为我们始终是在左侧添加权值，所以 $state\lt 0$ 的部分用不到，可以减枝

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <iomanip>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
ll dp[20][20][2000];//
vector<int> c;
ll dfs(int pos, int x, int sta, bool lim)
{
    if (pos == -1)
        return sta == 0;
    if (sta < 0)
        return 0;
    if (!lim && dp[pos][x][sta] != -1)
        return dp[pos][x][sta];
    int up = lim ? c[pos] : 9;
    ll ret = 0;
    for (int i = 0; i <= up; ++i)
    {
        ret += dfs(pos - 1, x, sta + i * (pos - x), lim && i == c[pos]);
    }
    if (!lim && dp[pos][x][sta] == -1)
        dp[pos][x][sta] = ret;
    return ret;
}
ll slove(ll x)
{
    c.clear();
    do{
        c.push_back(x % 10);
        x /= 10;
    } while (x);
    ll ret = 0;
    for (int i = 0; i < c.size(); ++i)
    {
        ret += dfs(c.size() - 1, i, 0, 1);
    }
    return ret - c.size() + 1;
}

int main()
{
    memset(dp, -1, sizeof dp);
    int t;
    for (read(t); t--;)
    {
        ll l, r;
        read(l), read(r);
        printf("%lld\n", slove(r) - slove(l - 1));
    }
}

动态规划-数位DP

问题

举例

HUD-2089 不要62

题意

思路

例题

hdu 3702 Balanced Number

题目大意

解题思路

数位DP好难啊