(没学懂,待填坑)【动态规划】数位动态规划
知识点
一 . 数位DP
数位DP是与数位相关的一类计数类DP,一般用于统计区间[l,r]满足特定条件的数位元素个数。数位指个位、十位、百位、千位等,数位DP指的就是在数位上进行动态规划。数位DP实质上就是有策略的枚举,子问题求解后进行记忆化搜索即可。
二 . 需要注意
① 记忆化 ②约束条件 ③高位前导0
三 . 数位DP模板
模板题
1 . 洛谷 P4999 烦人的数学作业
思路:该题要求在区间内的数字各个数位相加所得的和,但是看数据范围,可以发现数据范围很大,不能通过暴力做法。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll int T,l,r;
const int maxn=1e7+5,mod=1e9+7;
ll int dp[305][305],a[maxn];
inline ll int read()
{
ll int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline ll int solve(ll int pos,ll int res,ll int limit)
{
if(!pos) return res;
if(!limit && dp[pos][res]!=-1) return dp[pos][res];
int top=limit?a[pos]:9;
ll int result=0;
for(int i=0;i<=top;++i)
{
result=(result+solve(pos-1,res+i,limit && i==top))%mod;
}
if(!limit) dp[pos][res]=result;
return result;
}
inline ll int make(ll int x)
{
ll int num=0;
while(x)
{
a[++num]=x%10;
x/=10;
}
return solve(num,0,1)%mod;
}
int main()
{
T=read();
memset(dp,-1,sizeof(dp));
while(T--)
{
l=read(); r=read();
printf("%lld\n",(make(r)-make(l-1)+mod)%mod);
}
return 0;
}