原题链接https://ac.nowcoder.com/acm/contest/5671/H

题目描述

设S(x)表示十进制表示下x的每位数字之和，当S（A）>S（B）时，(A,B)表示一个和谐对。
给定N，求满足 的和谐对（A，B）的数量，答案对 取模。

输入描述

• 只有一行整数N（ ）。

输出描述

• 输出一个整数作为答案。

样例

• 输入
  100
• 输出
  967

题解思路

首先最吸引人眼球的应该是N的取值范围了，一看就会让人联想到高精度。
想什么呢
跟数字有关，当然是数位dp而非高精。
作为数位DP，自然就有暴力枚举记忆化。
根据题意，可以定义dp数组的维度[pos][A][B][l1][l2]。但用头发想想就知道，这么sao6的数组显然是开不下的。所以需要精简一下，把第二第三维度压缩为一个维度[sum]。

• pos指位置；
• sum指当前的A与B之和（但要小心，可能是负数）；
• l1限制 ；
• l2限制 .

行，DFS细节详见代码。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int MAXN=110;
int n,a[MAXN],dp[MAXN][MAXN*20][2][2];
char s[MAXN];
int dfs(int x,int d,int  lim1,int lim2)
{
    if(!x) return d>1000;
    if(~dp[x][d][lim1][lim2]) return dp[x][d][lim1][lim2];
    int ret=0,lim=lim1?a[x]:9;
    for(int i=0;i<=lim;i++)
        for(int j=0;j<=(lim2?i:9);j++)
            ret=(ret+dfs(x-1,d+j-i,lim1&(a[x]==i),lim2&(i==j)))%mod;
    return dp[x][d][lim1][lim2]=ret;     
}
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
        a[len-i]=s[i]-'0';
    printf("%d",dfs(len,1000,1,1)%mod);
}