题解 | #选择困难症#

dfs搜索，通过>M这个条件进行剪枝， 先对每类物品的数组进行排序，如果在某个节点已经大于M的时候，以下的分支的个数都可以用乘法得出。

#include<iostream>
#include<algorithm>
using namespace std;

int k,M;

int arr[7][110];
int len[7];
long long temsum;
long long dfs(int round){
    long long ans=0;
    if(round>=k){
        if(temsum>M){
            return 1;
        }else{
            return 0;
        }
    }else{
        ans+=dfs(round+1);//empty
        for(int j=0;j<len[round];++j){
            if(temsum+arr[round][j]>M){
                long long now=len[round]-j;
                for(int t=round+1;t<k;++t){
                    now*=len[t]+1;//including empty
                }
                ans+=now;
                break;
            }else{
                temsum+=arr[round][j];
                ans+=dfs(round+1);
                temsum-=arr[round][j];
            }
        }
        return ans;
    }
}

int main(){
    while(cin>>k>>M){
        temsum=0;
        for(int i=0;i<k;++i){
            cin>>len[i];
            for(int j=0;j<len[i];++j){
                cin>>arr[i][j];
            }
            sort(arr[i],arr[i]+len[i]);
        }
        cout<<dfs(0)<<endl;
    }
}