正解:背包
解题报告:
好烦昂感觉真的欠下一堆,,,高级数据结构知识点什么的都不会,基础又麻油打扎实NOIp前的题单什么的都还麻油刷完,,,就很难过,,,哭辣QAQ
不说辣看这题QwQ!
首先注意到当i>=√n时相当于是有无穷个的
可以想到对不同的物品数量进行分类讨论
对于i<√n,就最普通的背包,f[i][j]:第i个物品已装容量为j的方案数
转移就是f[i][j]=∑f[i-1][j-k*i](0<=k<=i)(这个显然可以降维变成f[i]:容量为i的方案数
然后这儿有两种优化方法,分别港下QwQ
1)
首先想到最朴素的算法就是枚举ijk,布吉岛能不能过,应该布星不然为什么要优化×
所以考虑优化,就,另开数组sum[i]:容量为i的方案数
我知道听起来跟一样的似的,,,其实sum有点类似于f的替代品,只是因为转移的时候如果直接修改f的值是布星的,修改前后的值都要存下来,所以开了俩数组(,,,还是麻油表达好,下午港QAQ
然后在转移的时候就是这样的:
对于sum数组,就跟完全背包转移一样的,从小到大地for转移一下
然后就从sum转移到f
完全背包和多重背包的转移就在于个数的限制嘛,所以从sum转移到f的时候只要判断一下j的大小
如果j<=i*i,j就能从所有小于等于它的转移过来,不用管
如果j>i*i,就不是能从所有小于等于它的转移过来的(因为物品数量的限制嘛QwQ
所以要减去不能转移过来的,也就是sum[j-i*i]
然后就转移完辣
2)
仔细看转移方程,设j-k*i=j0,显然j和j0在%i意义下同余
这样子再对剩余系做个前缀和,也是可行的,而且更快一些,但是难理解一些我理解了半天QAQ
这两种的代码我都会放的QwQ
然后对于i>=√n,就相当于是麻油个数限制了鸭,所以就相当于是跑个完全背包辣
然后问题就转化成了整数划分问题,要求出一个和为n,最小数>=√n的序列,为了防重,强制设定该序列为一个单调不下降序列w
那转移就是,要么直接在序列的最前面加上一个√n,要么全部+=1
显然这样就可以不重不漏地构造出所有的方案了
那就是设g[i][j]:分出了i个数,和为j的方案数
由上面得出的转移可以列出转移方程:g[i][j]=g[i][j-i]+g[i-1][j-√n]
最后把两部分拼凑在一块儿就乘法原理+加法原理,最基础的小学奥数思想不说辣QAQ
具体代码中午放趴QAQ