选择困难症

教我***儿子做题.
https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.
我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
const int M=1e6+5;
int k,m;
int a[10];
int v[10][N];
ll ans=0;
ll w[M];
ll tot=0;
void dfs1(int u,int val)
{
    if(u>k/2)
    {
        w[tot++]=val;
        return;
    }
    for(int i=1;i<=a[u];i++)
    {
        dfs1(u+1,val+v[u][i]);
    }
    dfs1(u+1,val);
}//预处理k/2的

void dfs2(int u,int val)
{
    if(u>k)
    {
        ans+=tot-(upper_bound(w,w+tot,m-val)-w);
        return;
    }
    for(int i=1;i<=a[u];i++)
    {
        dfs2(u+1,val+v[u][i]);
    }
    dfs2(u+1,val);
}

int main()
{
    while(cin>>k>>m)
    {
        ans=0;tot=0;
        for(int i=1;i<=k;i++)
        {
            cin>>a[i];
            for(int j=1;j<=a[i];j++)
            {
                scanf("%d",&v[i][j]);
            }
            sort(v[i]+1,v[i]+1+a[i]);
        }
        dfs1(1,0);//层数 价值
        sort(w,w+tot);
        dfs2(k/2+1,0);
        cout<<ans<<endl;
    }
    return 0;
}

另外一个方法就是直接dfs,但是这样绝对是可以卡的.代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int k,m;
int a[10];
int v[10][N];
ll ans=0;
void dfs(int u,int val)
{
    if(u>k+1)    return;
    if(val>m)
    {
        ll temp=1;
        for(int i=u;i<=k;i++)
        {
            temp*=(a[i]+1);
        }
        ans+=temp;
        return;
    }
    for(int i=1;i<=a[u];i++)
    {
        dfs(u+1,val+v[u][i]);
    }
    dfs(u+1,val);
}

int main()
{
    while(cin>>k>>m)
    {
        ans=0;
        for(int i=1;i<=k;i++)
        {
            cin>>a[i];
            for(int j=1;j<=a[i];j++)
            {
                scanf("%d",&v[i][j]);
            }
            sort(v[i]+1,v[i]+1+a[i]);
        }
        dfs(1,0);//层数 价值
        cout<<ans<<endl;
    }
    return 0;
}