题目描述
数位dp模板题
样例
blablabla
算法1
(数位dp+记忆化) $O(x)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int memo[40][40];
int a,b;
int f(string &s,int i,int mask,bool limt,bool num)
{
if(i == s.size()) return int(num);
if(!limt && num && memo[i][mask]!=-1) return memo[i][mask];
int res = 0;
if(!num) res += f(s,i+1,mask,false,false);
int up = limt?s[i]-'0':9;
for(int d=1-int(num);d<=up;d++)
{
if(d >= mask)
{
res += f(s,i+1,d,limt && d==up,true);
}
}
if(!limt && num) memo[i][mask] = res;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
while(cin>>a>>b)
{
memset(memo, -1, sizeof memo);
string s1(move(to_string(a-1)));
string s2(move(to_string(b)));
int res1 = f(s1,0,0,true,false);
memset(memo, -1, sizeof memo);
int res2 = f(s2,0,0,true,false);
printf("%d\n",res2-res1);
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla