- 科技
- 数学游戏（数位dp）
思路：dp[i]表示从0—i所有满足条件数的数量，然后对每一位考虑，如果当前位是大于等于前面一位的那么就加上此时满足条件的个数继续向下一位看，否则则后面的数都不满足直接退出。那么我们就需要知道在共i位时且最高位（最左端）是j的不降数（0<=j<=9）的个数有多少，我们用f[i][j]表示这个状态，那么可以发现当第i位是j时，他的数量一定是由i-1位且最高位是j-9之间的和那么可得f[i][j]+=f[i-1][j-9]，那么我们先预处理一下f[15][9]即可，然后dp求解
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e9+7;
const int N
=2e6+10;
const int M
=1e3+10;
const int inf
=0x3f3f3f3f;
const int maxx
=2e5+7;
const double eps
=1e-6;
int gcd(int a
,int b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll
qsm(int a
,int b
,int p
)
{
ll res
=1%p
;
while(b
)
{
if(b
&1)
res
=res
*a
%p
;
a
=1ll*a
*a
%p
;
b
>>=1;
}
return res
;
}
int f
[100][100];
void init()
{
for(int i
=0;i
<=9;i
++) f
[1][i
]=1;
for(int i
=2;i
<=15;i
++)
{
for(int j
=0;j
<=9;j
++)
{
for(int k
=j
;k
<=9;k
++)
{
f
[i
][j
]+=f
[i
-1][k
];
}
}
}
}
int dp(int n
)
{
if(!n
)return 1;
vector
<int> num
;
while(n
) num
.push_back(n
%10),n
/=10;
int res
=0;
int last
=0;
for(int i
=num
.size()-1;i
>=0;i
--)
{
int x
=num
[i
];
if(x
<last
)break;
for(int j
=last
;j
<x
;j
++)
res
+=f
[i
+1][j
];
last
=x
;
if(!i
)res
++;
}
return res
;
}
int main()
{
init();
int l
,r
;
while(cin
>>l
>>r
)
cout
<<dp(r
)-dp(l
-1)<<endl
;
return 0;
}
Processed:
0.091, SQL:
8
