• wd

    感觉题目的想法还是挺不错的.

    很明显是数位dp的题, 但是一开始没想出来, 因为之前做都是一个数满足什么什么条件, 这里是一对数满足什么什么条件.

    还是想一下怎么确定状态.

    1. 当前位.
    2. 位数和的差值. 这个状态很重要, 就是我们不需要知道前面具体选择了两个数的具体值, 只要知道差值就好了
    3. 前面选择的位是否相等. 这个是必要的, 因为位数和的差值为0并不代表前面选择的都是相同的.

    这三个就可以确定完状态了.

    然后每次状态转移的时候. 如果前面选择的位都是相同的, 那么此时这位, 第二个数只能选择小于等于第一个数的.

    如果前面第二个数已经小于第一个数了, 那第二个数就可以随便选了. 就和字典序是一样的.

  • 细节

    有两个细节问题一开始没处理好.

    1. 位数和的差值.

      这个差值是会为负的, 所以要把零点设置到1000

    2. limit的状态

      以前写数位dp都没把高位限制放到状态里, 也能过. 但是这题就T了. 所以要把高位限制放到状态里

  • 时间复杂度

    就是dp的状态数. 因为最多到100位, 所以位数和的差值最大是. 正负还要乘2.

    状态数就是. 

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int mod = 1e9 + 7;
char s[N];
int digit[N];
int dp[N][2005][2][2];

void add(int &a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
int t;

int dfs(int len, bool limit, int gap, bool equal)
{
    if (dp[len][gap][(int)equal][limit] != -1)
        return dp[len][gap][(int)equal][limit];
    if (len == 0)
        return gap < 1000;
    int up = limit ? digit[len] : 9;
    int ans = 0;
    for (int i = 0; i <= up; i++)
    {
        if (equal)
        {
            for (int j = 0; j < i; j++)
                add(ans, dfs(len - 1, limit && (i == up), gap + i - j, false));
            add(ans, dfs(len - 1, limit && (up == i), gap, true));
        }
        else
        {
            for (int j = 0; j <= 9; j++)
                add(ans, dfs(len - 1, limit && (i == up), gap + i - j, false));
        }
    }
    dp[len][gap][(int)equal][limit] = ans;
    return ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%s", s);
    int l = strlen(s);
    for (int i = 0; i < l; i++)
    {
        digit[i + 1] = s[l - i - 1] - '0';
    }
    cout << dfs(l, 1, 1000, 1) << endl;
    return 0;
}

```