用于: 统计数位于数位的相关信息的计数问题,
通常会问在某个区间内, 利用减法思维,这样就会减少一个边界的判断
此时就会只有一个边界, 这个边界 利用 lim 处理, 在暴力枚举的时候不要超过lim 就行了
记忆化搜索的过程, 就是一个完全的暴力, 不过有记忆化搜索, 所以他的时间复杂度是 DP的空间+ 点点边界内容
一般就二维dp[][], 第一个维度 是 pos, 第二个维度是 状态, 这个维度来表示什么东西来解决当前问题是核心, 具体就看模板:
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define int long long const int maxn=1000100; const int mod=1e9+7; int t; int l,r; int a[maxn],num; int dp[200][200]; int dfs(int a(postion),int statement,bool lmt){ if(!a) return ; if(!lmt&&dp[x][statement]!=-1) return dp[a][statement];//最高位是0也直接返回 int bound=top?p[x]:9;//根据top判断枚举的上界bound int ans=0; for(int i=0;i<=bound;i++) { // 状态处理 ans += dfs(a-1,statment,lmt&&(i==bound)); } if(!lim) dp[a][statement]=ans; return ans; } int solve(int x){ int sum=0; while(x){ p[++sum]=x%10; x/=10; } return dfs(sum,0,1)%mod;//从最高位开始枚举 } signed main(){ cin>>t; memset(f,-1,sizeof(f)); while(t--){ cin>>l>>r; cout<<(solve(r)-solve(l-1)+mod)%mod<<'\n'; } return 0; }
例子:
题目 :将每一个[l,r]中的数字的每一位的数加起来, L ,R <=1e18;
statement 设置为 前面几位的sum, dp[i][sum] 表示前几位的sum时,后面一共有多个和
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define int long long const int maxn=1000100; const int mod=1e9+7; int t; int l,r; int a[maxn],num; int f[200][200]; int dfs(int x,int sum,bool top){//我个人认为这很像类似递归算法 if(!x) return sum;//如果已经到了最后一位就可以直接返回sum if(!top&&f[x][sum]>=0) return f[x][sum];//最高位是0也直接返回 int bound=top?a[x]:9;//根据top判断枚举的上界bound int ret=0; for(int i=0;i<=bound;i++) ret=(ret+dfs(x-1,sum+i,top&&i==bound))%mod; /* 这里大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论 去计算不同情况下的个数，这里一定要保存枚举的这个数是合法 */ if(!top) f[x][sum]=ret;//这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑top，这里就是top就完全不用考虑了* return ret; } int solve(int x){ int sum=0; while(x){ a[++sum]=x%10; x/=10; } return dfs(sum,0,1)%mod;//从最高位开始枚举 } signed main(){ cin>>t; memset(f,-1,sizeof(f)); while(t--){ cin>>l>>r; cout<<(solve(r)-solve(l-1)+mod)%mod<<'\n'; } return 0; }