思路
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define N 15
int f[N][N];//f[i][j]表示i位数且最高位为j的不降序的方案数
void init()//dp过程
{
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++)
for(int k=j;k<=9;k++)//状态划分
f[i][j]+=f[i-1][k];
}
int dp(int n)
{
if(!n) return 1;//n=0,只有0这一种方案
//因为当n=0时,下面的while循环无法通过,所以要进行特判
vector<int> num;
while(n) num.push_back(n%10),n/=10;
int ans=0;
int lt=0;//保存上一位的最大值
for(int i=num.size()-1;i>=0;i--)
{
int x=num[i];
for(int j=lt;j<x;j++) //左边分支,因为要保持不降序,所以j>=lt
ans+=f[i+1][j];
if(lt>x) break;//如果上一位最大值大于x的话,不构成降序,所以右边分支结束
lt=x;
if(!i) ans++;//全部枚举完了也同样构成一种方案
}
return ans;
}
int main()
{
int n,m;
init();
while(cin>>n>>m) printf("%d\n",dp(m)-dp(n-1));
return 0;
}
这句代码的含义在我看来应该是:如果当前位的数字小于last,左分支结束,(比当前位高的位数的数字都是 n当中的原数字,也就是说已经确定了 , 所以当前位怎么枚举都不是满足条件的数字) 。同时,又因为我们的原数字不再可能是一个不降数字了,所以右分支结束。综上,如果出现当前为小于last的情况,我们直接退出了循环返回当前的ans 的值即可。(不知道我这样理解对不对,欢迎交流)。
我也是这样想的,感觉数位DP就是把那个树给描述了一遍,走下去的条件就是能进入右子树
q请问一下为什么这道题不用特殊处理前导0的情况呢,而Windy数需要特殊处理呢
因为本题包不包含前导0最后结果都相同 而windy数明确不能出现前导0 所以在dp时需要跳过最高位是0的情况 而后面数位上的数可以是0 最后再将跳过了的但符合条件的数再加上
也就是说,数位DP每一位上都必须填上某个数,不能跳过,有的题使用前导0对答案无影响,有的需要考虑一下前导0产生的影响。
大佬,图借用下。
STO
qp
Orz
if(lt>x) break;//如果上一位最大值大于x的话,不构成降序,所以右边分支结束
这里应该是“非降序”吧
你说得对