物品选择wa30分求大佬康康

[郑涞允1 (门酱)]

#include<bits/stdc++.h>
using namespace std;
int k,m,a[10][110],f[10];
long long ans;
void dfs(int x,long long s){
	if(x==k+1){
		if(s>m)ans++;
		return;
	}if(s>m){
		long long n=1;
		for(int i=x;i<=k;i++){
			n=n*(f[x]+1);
		}ans+=n;
		return;
	}for(int i=0;i<=f[x];i++){
		dfs(x+1,s+a[x][i]);
	}
}
int main(){
	cin>>k>>m;
	for(int i=1;i<=k;i++){
		cin>>f[i];
		for(int j=1;j<=f[i];j++){
			cin>>a[i][j];
		}
	}dfs(1,0);
	cout<<ans;
	return 0;
}

[张瑜]

@郑涞允1

if(s>m){
		long long n=1;
		for(int i=x;i<=k;i++){
			n=n*(f[x]+1);
		}ans+=n;
		return;

有没有hack数据？然后我问一下，我看了代码之后，想确认一下，您的思路是不是就是跑一遍dfs，如果每类物品都搜完了，就记录方案，然后做了一个剪枝，如果已经大于了，那么剩下的选不选无所谓，就是分选或者是不选的，然后如果没有，那么继续搜索。是这样的吗？

[郑涞允1 (门酱)]

是的

[张瑜]

你能下一组数据吗？

[张瑜]

因为我看着这个思路每什么问题，最多我认为加的特判就是一开始如果全部最大都不行就是 0 。

[郑涞允1 (门酱)]

输入
5 37
29 26 26 34 45 29 22 37 28 40 15 38 46 48 23 42 17 28 24 21 14 42 28 35 15 17 34 36 20 47
21 30 23 28 38 15 29 14 15 42 18 50 35 20 18 12 10 28 23 49 26 22
15 22 31 50 31 39 30 21 48 33 15 30 50 37 14 28
27 15 28 24 29 11 38 14 48 33 18 19 25 25 15 15 41 14 41 31 35 38 50 27 49 15 33 38
37 41 38 30 35 12 46 19 11 39 45 23 15 25 29 33 36 42 41 29 48 18 29 34 31 50 26 28 29 43 42 23 18 33 17 18 36 21
目标输出
11235120
实际输出
4798880

[周子寓 (zzy10124)]

你解决方案给自己什么意思？？？
直接分组背包啊
@郑涞允1