首先我们设 dp[i][x][y][k] 表示当前到了第 i 层,这一层 x 个芽(还可以继续生长的节点),下一层 y 个芽,已经选择了k个叶子(使k个节点变成叶子节点)
转移的话就直接枚举一下y 这一层有 p 个变为叶子节点即可,然后算上结束的代价
可以用前缀和优化一下。设sum[i]表示i之前的数出现的次数之和
dp[i][x][y][k]=min(dp[i+1][x+y-p][x-p][k+p]+sum[n]-sum[k+p])
这里是倒着推
考虑优化
我们发现第一维似乎没什么用
不如把它省掉
我们设 dp[x][y][k] 表示最下方一层 x 个芽,下一层 y 个芽,已经选择了k个叶子。
转移的时候就直接枚举 y 这一层结束了 p 个,注意这里代价不是每一个元素结束的时候记上了,我们在没往下一层时,我们算一下这一层会产生的贡献。
dp[x][y][k]=min(dp[y+x-p][y-p][k+p]+sum[n]-sum[k+p])
复杂度o(n^4)
这个复杂度还是不行
显然状态已经优化不了了,考虑优化转移
现在的转移是o(n)的,因为枚举p的原因
我们不如每一次选一个点,到不想选的时候再跑到下一层去
dp[x][y][k]=min(dp[x][y-1][k+1],dp[x+y][y][k]+sum[n]-sum[k])
复杂度O(n^3)
这个题显然是数位dp,枚举模数就好了
然后重点不是在这里
我竟然在初始化上挂掉了?
注意这里每次dp之前都要初始化,但是并不能每次都memset,这样会炸!
我们只需要把用过的初始化就行了。
然而这样还是不行!!!
我们在用前缀和的思想的时候相当于清空了两遍
而这是没必要的
然后就a了
qwq