解法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]],等式右边分别表示替换和保留方案数。