c/c++语言开发共享Harmony Pairs 2020牛客暑期多校训练营（第六场）

https://ac.nowcoder.com/acm/contest/5671/H

第一版只有我们队没过H。。。。

我们只会分情况讨论，a的位数小于b的位数的时候求个方案数，a的位数等于b的位数的时候数位dp求方案数，队友调了快一个多小时，赛后过了。。。

然而直接在一个dfs里面枚举b<=n和a<=b的大小关系，然后枚举差值，巨简单。。

f[k][sum][fb][fa]表示现在枚举到第k位，S(B)-S(A)+1000=sum，fb==1为前k位于n相等，0为已经<n,fa==1表示前k位A=B,0为A<B，此时最后能S(B)-S(A)+1000<1000的方案数

然后根据枚举第k位A和B分别放哪个数，根据fb,fa设个上限，让B<=N和A<=B始终成立就行了

 #include<bits/stdc++.h> using namespace std; typedef long long ll;  const int maxl=102; const int mid=1000; const int mod=1e9+7; int n; int a[maxl]; ll dp[maxl][mid*2][2][2]; char s[maxl];  inline void prework() { 	scanf("%s",s+1); 	n=strlen(s+1); 	for(int i=1;i<=n;i++) 		a[i]=s[i]-'0'; }  inline ll dfs(int k,int sum,bool fb,bool fa) { 	if(k>n) 		return (ll)(sum<mid);  	if(dp[k][sum][fb][fa]!=-1) 		return dp[k][sum][fb][fa]; 	ll ret=0; 	for(int i=0;i<=(fb?a[k]:9);i++) 		for(int j=0;j<=(fa?i:9);j++) 			ret=(ret+dfs(k+1,sum+i-j,fb&&(i==a[k]),fa&&(j==i)))%mod; 	dp[k][sum][fb][fa]=ret; 	return ret; }  inline void mainwork() { 	memset(dp,-1,sizeof(dp)); 	printf("%lldn",dfs(1,mid,1,1)); }  int main() { 	prework(); 	mainwork(); 	return 0; }

c/c++开发分享Harmony Pairs 2020牛客暑期多校训练营（第六场）地址：https://blog.csdn.net/liufengwei1/article/details/107620761