杭州网站提升排名,中石油工程建设公司网站,开发游戏的公司,阿里云服务器可以访问国外网站吗思路#xff1a; 之前想直接开左右两边的数结果爆内存... 枚举每次pivot的位置#xff0c;然后数位DP#xff0c;如果sum0返回0#xff0c;因为已经小于零说明已经到了pivot右边#xff0c;继续dfs只会越来越小#xff0c;且dp数组会炸 注意一下一些细节#xff1a;… 思路 之前想直接开左右两边的数结果爆内存... 枚举每次pivot的位置然后数位DP如果sum0返回0因为已经小于零说明已经到了pivot右边继续dfs只会越来越小且dp数组会炸 注意一下一些细节dp开long long注意前导零只能算一次 代码 #includeiostream
#includealgorithm
#define ll long long
const int N 500005;
const int INF 0x3f3f3f3f;
using namespace std;
int dig[20];
ll dp[20][20][2000];
ll dfs(int pos,int piv,int sum,bool limit){if(pos -1) return sum 0? 1 : 0;if(sum 0) return 0;if(!limit dp[pos][piv][sum] ! -1) return dp[pos][piv][sum];int top limit? dig[pos] : 9;ll ret 0;for(int i 0;i top;i){int tot;if(pos piv){tot sum (pos - piv)*i;}else if(pos piv){tot sum - (piv - pos)*i;}else{tot sum;}ret dfs(pos - 1,piv,tot,limit i top);}if(!limit) dp[pos][piv][sum] ret;return ret;
}
ll solve(ll x){int pos 0;if(x -1) return 0;while(x){dig[pos] x % 10;x / 10;}ll ret 0;for(int i 0;i pos;i){ret dfs(pos - 1,i,0,true);}return ret - pos 1; //前导零只能算一次
}
int main(){int T;ll l,r;scanf(%d,T);while(T--){memset(dp,-1,sizeof(dp));scanf(%lld%lld,l,r);printf(%lld\n,solve(r) - solve(l - 1));}return 0;
}转载于:https://www.cnblogs.com/KirinSB/p/9408772.html
