关于dp方案数为负数
  • 板块学术版
  • 楼主Qin_windlight
  • 当前回复7
  • 已保存回复7
  • 发布时间2025/7/23 10:39
  • 上次更新2025/7/23 15:20:58
查看原帖
关于dp方案数为负数
1490511
Qin_windlight楼主2025/7/23 10:39

https://www.luogu.com.cn/problem/P4141 题中,第二篇题解的状态转移方程if(jv[i]>=0)f[j][1]=(f[j][0]f[jv[i]][1]+10)if(j-v[i]>=0) f[j][1]=(f[j][0]-f[j-v[i]][1]+10)%10;

但是在转移中可能会出现负数,但由于题目让求个位数的值,加上10再%10,这样解释我还可以接受

我去问AI为什么会出现负数,AI告诉我

在用“差分”或“容斥”这类技巧做动态规划的时候,出现负数的中间状态并不意味着「真的有负的方案数」,它只是一个**“调整量”**,用来剔除重复计数或修正过多计入的部分。只要最终你把这些中间状态正确地“拼”回来(比如再加上被减掉的部分、或者在模意义下取余),结果一定是非负的真实方案数。

但是在这个式子中,f[j][1]只被计算了一次,就是说他最终的方案数可能是负数

我又想如果我不只求体积为j,删去x的方案数的个位数,我要求体积为j,删去x的方案数,如果这样的话怎么办?

我现在可以想明白为什么有负数,就是根据

使用i体积j的方案数=不用i体积j的方案数+使用i体积ji的体积的方案数使用i体积j的方案数 = 不用i体积j的方案数 + 使用i体积j-i的体积的方案数

但是我想不明白为什么有负数他的方案数也是正确的,并且为什么+10%10他就是正确的。还有就是如果要求方案数而不是方案数的个位怎么办

希望有大佬可以解答一下

2025/7/23 10:39
加载中...