2020牛客暑期多校训练营（第六场）H.Harmony Pairs 数位DP

题目链接：https://ac.nowcoder.com/acm/contest/5671/H
题目大意：
s(x)=x在十进制下所有位的数字之和。s(123)=1+2+3=6
现在给你一个n。问：满足0<=x<=y<=n并且s(x)>s(y)的(x, y)的对数。

思路：看出来是数位DP了。但是不知道两个数怎么搞。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1e9+7;

char s[105];
LL f[105][2005][2][2][2];
//pos初始值为1000，防止负数产生
LL DFS(int pos, int sum, int va, int vb, int limit){
    if(pos==0){
        return sum>1000;//s(x)-s(y)>0
    }
    if(f[pos][sum][va][vb][limit]!=-1){
        return f[pos][sum][va][vb][limit];
    }
    int na=va?(s[pos]-'0'):9;
    int nb=vb?(s[pos]-'0'):9;
    LL res=0;
    for(int i=0; i<=na; i++){//枚举这位x的值
        for(int j=0; j<=nb; j++){//枚举这位y的值
            if(!limit&&i>j){//如果之前没有x<y，这位x的值不能比y的值大
                continue;
            }
            res+=DFS(pos-1, sum+i-j, va&&i==na, vb&&j==nb, limit||j>i);
            res%=mod;
        }
    }
    return f[pos][sum][va][vb][limit]=res;
}

int main() {
    memset(f, -1, sizeof(f));
    scanf("%s", s+1);
    int n=strlen(s+1);
    int L=1, R=n;
    while(L<R){
        swap(s[L], s[R]);
        L++, R--;
    }
    printf("%lld\n", DFS(n, 1000, 1, 1, 0));

    return 0;
}