题目描述
这是一道数位dp题,由于比赛的时候没学过数位dp所以没做出来,这两天恶补了一下这方面的知识,跟着提高课学了y总数位dp的板子,尽管感觉自己学得不是很到位,但再次尝试本题时思路并为受阻,很快就ac了。学过提高课的话下面这份代码理解起来应该很快,但是它真的跑得很慢。。。。。。(我是废物,,,,,,,
代码解释
f数组表示总共有i位且最高位是j的情况下总和为s的方案数。
init函数:
第一个for是指1个数的情况,总共只有1位,最高位是i,和也是i,方案数为1
接下来遍历位数i
枚举最高位j
枚举次高位k
枚举总和s
最高位为j总和为s的方案数 == 次高位为k总和为s-j的方案数之和
主函数:
首先要把数字字符串转换成vector,然后还得reverse一下(这样倒着遍历,好求位数
由于题目是两个范围内的方案数,所以这里可以利用两次前缀和思想
求num1 - 1和num2的方案数max_sum - (max_min - 1),故这里涉及到要把num1 - 1(sub函数)
sub函数:
从最低位开始往前找,如果是0就变9,不是0就减1
判断最高位是否为0,删掉最高位的0(只有可能出现1个0,判断语句即可)
dp函数:
res保存答案,last存前面所有数的和,初始为0
for循环从高位开始枚举,取出当前这一位数字x
先计算左分枝,当前这一位填小于x的数j,那么我的总和至少为j至大不能超过最大值maxn减去前面的总和last,累加答案
接下来计算右分枝,如果last + x大于maxn了那说明没有右分枝了,直接break,否则更新last
如果很幸运走到了最后,last依然小于maxn,那么res++
最后返回res即可
C++ 代码
const int MOD = 1e9 + 7;
class Solution {
public:
int f[24][11][410];
int max_sum;
void init()
{
for (int i = 0; i <= 9; i ++) f[1][i][i] = 1;
for (int i = 2; i < 24; i ++)
for (int j = 0; j <= 9; j ++)
for (int k = 0; k <= 9; k ++)
for (int s = 0; s <= max_sum; s ++)
if (s >= j) f[i][j][s] = (f[i][j][s] + f[i - 1][k][s - j]) % MOD;
}
int dp(vector<int>& nums, int maxn)
{
int res = 0, last = 0;
for (int i = nums.size() - 1; i >= 0; i --)
{
int x = nums[i];
for (int j = 0; j < x; j ++)
for (int k = j; k <= maxn - last; k ++)
res = (res + f[i + 1][j][k]) % MOD;
if (last + x <= maxn) last += x;
else break;
if (!i && last <= maxn) res ++;
}
return res % MOD;
}
void sub(string &s)
{
int n = s.size();
for (int i = n - 1; i >= 0; i --)
if (s[i] == '0') s[i] = '9';
else
{
s[i] --;
break;
}
if (s[0] == '0' && s.size() > 1) s = s.substr(1);
}
int count(string num1, string num2, int min_sum, int max_sum) {
this->max_sum = max_sum;
memset(f, 0, sizeof f);
init();
vector<int> n1, n2;
sub(num1);
for (auto i: num2) n2.push_back(i - '0');
for (auto i: num1) n1.push_back(i - '0');
reverse(n2.begin(), n2.end());
reverse(n1.begin(), n1.end());
int ans1 = (dp(n2, max_sum) - dp(n2, min_sum - 1) + MOD) % MOD;
int ans2 = (dp(n1, max_sum) - dp(n1, min_sum - 1) + MOD) % MOD;
return (ans1 - ans2 + MOD) % MOD;
}
};
好!
大佬
能问一下为什么 DP 里面
“先计算左分枝,当前这一位填小于x的数j,那么我的总和至少为j至大不能超过最大值maxn减去前面的总和last,累加答案”
至少为什么是 j 而不是 last + j 呢
前面几位应该都是从右分支下来的
也就是说 last 应该是 取满的
所以最大值不能超过 maxn - last
但是改了答案就错了