AcWing 1082. 数字游戏（数位dp）

题意：

定义 “不降数”：满足从左到右各位数字呈非下降关系的数字，如 123，446

现指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

思路：

这道题仍旧可以延续上一题AcWing 1081. 度的数量的思考方式，

把 N 的每一位（假设一共有 n 位）存储到数组中去，从最高位依次枚举，

对于每一位，我们有两个分支，我们以第一位为例子：

• 填 0 ~ a(n) - 1 中的任意数字，记为 x。
  

• 填 a(n) 的方案，后续往下继续细分第n - 1位。
  

  
  

• 对于分支一（左分支）：

x 在前面，后面有 n - 1 个位子，形如：x _ _ _ _ _ _ _ _

这种方案数可以通过动态规划（其状态表示和状态计算的分析在后面）递推快速算出预处理，

设f[i][j] 表示为 i 位数，并且最高位为 j 的不降序方案数

所以，左分支方案总数可以表示为：f[n][x]（x = 0、1、2、…、a(n) - 1）求和

• 对于分支二（右分支）：

因为要满足不降序的条件，所以当 a(n - 1) < a(n) 时才能继续进行，

并且在枚举左边的分支时，x ∈ 0 ~ a(n - 1) - 1时也同样需要满足 x < a(n)，不满足的话 break 即可，

当枚举到 第一位a1时，相当于 把所有位置都枚举完了，所以也算是一种方案数，要加入方案数

接下来就是是用于预处理状态的 dp 分析：

f[i][j]状态表示：

• 集合：所有最高位是 j，且一共有 i 位的不降数的集合

• 属性：数量

f[i][j]状态计算：

由于集合中所有子集的最高位已经固定（后方i - 1位不固定），且为 j ，我们不妨枚举倒数第 2 位的填法将集合划分成若干类，第 2 位可能填的数为：j、j+1、j+2、...、9（不下降）

假设次高位（倒数第 2 位）填的数为 k ，根据定义，此类子集的方案数为：f[i-1][k]

根据总集合方案数等于各个子集方案数相加，我们得出状态转移方程：

f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j + 1 ] + . . . + f [ i − 1 ] [ 9 ] f[i][j] = f[i-1][j] + f[i-1][j+1] + ... + f[i-1][9] f[i][j]=f[i−1][j]+f[i−1][j+1]+...+f[i−1][9]

据此，我们就可以预处理出我们所需要的状态。

代码：

#include

using namespace std;
const int N = 15;
typedef vector vi;
#define pb push_back
#define pp pop_back
int f[N][N];//f[i][j]表示一共有 i 位，且最高位为 j 的不下降数的个数
int a, b;

void init()
{
        for(int i=0; i<=9; ++i) f[1][i] = 1;//初始化：如果只有 1 位数，且最高位为某个数字，那么方案数就是 1
        for(int i=2; i=0; --i)//从最高位开始枚举
        {
                int t = num[i];
                for(int j=last; jt) break;//判断当前位能否填入 t ，即是否能形成“不下降”
                last = t;
                if(!i) ++res;//枚举完最后一位，加上一个方案数
        }
        return res;
}

int main()
{
        init();
        while(cin>>a>>b) cout<

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/662195.html