题目描述
[a,b]中有多少个不降数.
树形DP
算法思路
定义f(n):[0,n]中不降数个数.
若x属于f(n), 则x满足: 1.x是不降数 2.x∈[0,n]
求解是先将n的各位拆分为a[k-1]a[k-2]...a[0],从高位到低位进行分类讨论(集合划分).
左子树没有了n的限制,所以可以直接求满足条件的不降数,而右子树受n的限制需要进一步讨论.
不降数的直接求解可以用动态规划预处理.一般树形DP的DP过程在预处理中体现.
ysDP
状态表示
dp[i][j]
集合:最高位为j且共有i位的不降数的集合
属性:数量
状态计算
最高位已确定,可以根据次高位划分集合.次高位k∈[j,9],先不考虑最高位,则我们需要计算
最高位为k且共有i-1位的不降数的个数.dp[i][j] = ∑dp[i-1][k]
C++ 代码
#include <vector>
#include <iostream>
using namespace std;
const int N = 12;
int dp[N][10];
void init()
{//预处理不降数
for( int j = 0; j <= 9; j++ ) dp[1][j] = 1;
for( int i = 2; i < N; i++ )
{
for( int j = 0; j <= 9; j++ )
{
for( int k = j; k <= 9; k++ )
dp[i][j] += dp[i-1][k];
}
}
}
int f(int n)
{
//这里的不降数和特殊情况都把全0当作一种合理方案
if( !n ) return 1;//0特殊讨论
vector<int> nums;
while( n ) nums.push_back( n % 10 ), n /= 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 += dp[i+1][j];
}
if( x < last ) break; //右子树不满足条件
last = x;
if( !i ) res++; //一路限制 也就是n的表示满足不降数
}
return res;
}
int main()
{
init();
int l, r;
while( cin >> l >> r )
cout << f(r) - f(l-1) << endl;
return 0;
}