P2518 [HAOI2010] 计数 题解

· · 题解

一个纯数位 DP，不需要数学的做法。

题目 P2518

给你一个整数 n 你可以任意排列它各个位上的数，求产生的所有数中，比 n 小的数有多少个。

分析

按照一般数位 DP 的做法，我们需要在 DFS 的过程中枚举每个位置上填什么并记忆化搜索。

最基本的 DP 状态：dp[pos][limit]。分别代表着，第 pos 位，是否顶着上界。

此题不同的是，我们使用的 0~9 的个数是有限的，所以我们还需要的一维状态是当前每个数还剩几个可以使用。

对于维护每个数还剩几个可以用，一般想到的都是开个数组 num[i] 表示数字 i 还剩 num[i] 个。那么怎么把它加到 DP 状态里呢？

我的做法是:

map<vector<int>,long long> dp[55][2];

vector 的大小开到 10，第 i 位代表数字 i 使用的个数。

代码

我的代码