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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598433.html