欢迎光临散文网 会员登陆 & 注册

[ABC044C] 高橋君とカード

2023-07-08 13:29 作者:BNU_ACM  | 我要投稿
  • 解法1:多维的01背包

  • 解法2: 问题转换:在i处可选择保留a[i]或选择将a[i]替换为平均数x! 求使数组总和为x*n的方案数,减去1(全部替换的方案)。

  • f[i]表示总和还差i的方案数

  • f[n*x]=1表示初始情况下,总和为0,还差n*x

  • 更新f[j] = f[j+x] + f[j+a[i]],等式右边分别表示替换和保留方案数。


[ABC044C] 高橋君とカード的评论 (共 条)

分享到微博请遵守国家法律