这道是dp题,但我想不出状态转移方程,请神犇解答(不要引用chatGPT的回答)……
1条回答 默认 最新
- tanjunming2020 2023-04-01 19:28关注
看到数据范围,可以想到k个数的和不超过30000,可以先把30000以内的质数求出来
设f[i][s]表示当前已经选了i个数,这i个数的和为s的方案数,那么转移式为
f[i][s]+=f[i-1][s-x[j]]
f的初始值为f[0][0]=1
对于每个质数p,将f[k][p]求和即为答案
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用