题目链接

Game Bundles

分析

很神奇的一道题目
先想想如何计算一个集合和为60的子集个数
可以想到通过 \(DP\) 求解：
记 \(f[i][j]\) 为前 \(i\) 个数字，和为 \(j\) 的子集个数
则
\(f[i][j]+=f[i-1][j-a[i]]\)
\(f[i][a[i]]++\)
可以倒叙枚举 \(j\) 滚掉 \(i\) 这一维
代码如下

void sol(){
	for(int i=1;i<=n;i++){
		for(int j=60;j>=a[i]+1;j--) f[j]+=f[j-a[i]];
		f[a[i]]++;
	}
}

易发现，对于和为 \(60\) 的子集，其中值大于 &30& 的数最多有一个
也就是说，若在原集合中加入一个大于 \(30\) 的数 \(a\) , 则 \(f[60]+=f[60-a]\)

然后开始乱搞，
先随机一堆小于 \(30\) 的数，使其 \(f[60]\) 接近但不超过 \(m\)
然后将 \(f[1]\) ~ \(f[29]\) 从大到小排序，贪心地从大到小选择，即加入 \(60-i\)