AcWing 1082. 数字游戏
原题链接
中等
作者:
xiaoqi_
,
2021-04-17 12:27:37
,
所有人可见
,
阅读 311
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=15;
int f[N][N];
//预处理这里可以看作分类讨论,先当这位数字只有一位时,之后再枚举具有多位
void init()
{
for(int i=0;i<=9;i++) f[1][i]=1; //当只有一位数的时候
for(int i=2;i<N;i++)//当有多位时
for(int j=0;j<=9;j++)//第二位可以位0-9
for(int k=j;k<=9;k++)//下一个状态 因为时递增,所有未j到9
f[i][j]+=f[i-1][k]; //状态转移方程为:当前的状态+下一位数的状态
}
int dp(int n)
{
if(!n) return 1; //特判
vector<int> nums;
while(n) nums.push_back(n%10),n/=10; //转换为10进制(也可以转换为其他进制)
int res=0;
int last=0; //上一个状态
for(int i=nums.size()-1;i>=0;i--) //从最高位开始枚举
{
int x=nums[i]; //将当前位提取出来
for(int j=last;j<x;j++) //枚举下一个状态可以选的值
res+=f[i+1][j]; //当前的答案为:左端有i+1个数,当前的状态为j
if(x<last) break; //因为是递增数列,所有这种情况,不要
last =x; //状态转移
if(!i) res++; //如果枚举到最后一位,仍然没有break,那么这种情况成立
}
return res;//返回最终的结果
}
int main()
{
init();//初始化
int l,r;
while(cin>>l>>r) cout<<dp(r)-dp(l-1)<<endl; //类似于前缀和的写法
return 0;
}
最高位为什么是从开始,前导0显然不合法的呀,为什么这样是正确的
少见的纯逐句分析,好评