2020牛客多校第六场 （H-Harmony Pairs）

题目地址
题意： 给出$n$，然后求出从$0$到$n$有多少个数对，满足第一个数小于第二个数，但是第一个数的各位之和要大于第二个数

明显数位DP
好亏啊…明明不算难的题没写出来，开场就读到了，然后想不明白状态转移的方式…关于两个数需要满足大小顺序又要满足各位之和的要求，实在理不清，然后去写签到题和别的，就把这个丢了
主要是以前写过的所有数位DP都是对于范围内的一种数进行求解，第一次遇到关于数对的求解，有点懵逼…赛中实在想不出来，赛后看学长代码就理解了，我菜死了
首先最大为$10^{100}$,所以最大的数所有位都是9，最小的数就是0，各位之差不会超过1000，所以可以以1000打底来防止负数的出现
开一个数组$DP[105][2005][2][2][2]$
五个位置分别代表
当前搜索到的位置，
前面已经搜索出来的各位之差，
第一个数最高位此时是否有限制，
第二个数最高位此时是否有限制，
第二个数在前面是否已经大于了第一个数
然后就是常规的数位DP记忆化搜索了，关于$DFS$函数的书写是

LL DFS(int pos, int sum, bool lima, bool limb, bool limit) {
    if(pos < 0) {
        return sum > base;
    }
    if(DP[pos][sum][lima][limb][limit] != -1) {
        return DP[pos][sum][lima][limb][limit];
    }
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    LL res = 0;
    for(int i = 0; i <= up1; ++ i) {
        for(int j = 0; j <= up2; ++ j) {
            if(!limit && i > j) {
                continue;
            }
            res += DFS(pos - 1, sum + i - j, lima && i == up1, limb && j == up2, limit || j > i);
            res %= mod;
        }
    }
    return DP[pos][sum][lima][limb][limit] = res;
}

如果遍历完了（pos<0),就直接判断此时搜索出来的第一个数与第二个数之差，大于1000则代表大于（初始为1000），反之则不符合条件
同时$limit$代表前面是否第二个数已经大于第一个数，如果还没严格大于，那么这一位就不能进行$i>j$的操作，也就是

if(!limit && i > j) continue;

然后就很常规的数位DP了

$ps:$
从学长那学到一个数位DP的技巧，我一直都是记忆化搜索的时候先判断是否有$limit$，如果有则不进行记忆化，但是学长是单独开了一维状态代表是否有限制，这样每次都是记忆化搜索，空间换取时间更多了，学到了

全部代码是

#include <bits/stdc++.h>
using namespace std;
typedef long long  LL;
const LL mod = 1e9 + 7;
const int base = 1000;
string str;
LL DP[105][2005][2][2][2];
int len;
LL DFS(int pos, int sum, bool lima, bool limb, bool limit) {
    if(pos < 0) {
        return sum > base;
    }
    if(DP[pos][sum][lima][limb][limit] != -1) {
        return DP[pos][sum][lima][limb][limit];
    }
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    LL res = 0;
    for(int i = 0; i <= up1; ++ i) {
        for(int j = 0; j <= up2; ++ j) {
            if(!limit && i > j) {
                continue;
            }
            res += DFS(pos - 1, sum + i - j, lima && i == up1, limb && j == up2, limit || j > i);
            res %= mod;
        }
    }
    return DP[pos][sum][lima][limb][limit] = res;
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    memset(DP, -1, sizeof(DP));
    cin >> str;
    len = str.size();
    int L = 0, R = len - 1;
    while(L < R) {
        swap(str[L ++], str[R --]);
    }
    
    cout << DFS(len - 1, base, 1, 1, 0) << endl;
    return 0;
}

本文地址：https://blog.csdn.net/leoxe/article/details/107620745