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("%lld\n",dfs(1,mid,1,1));
}

int main()
{
	prework();
	mainwork();
	return 0;
}

本文地址：https://blog.csdn.net/liufengwei1/article/details/107620761