选择困难症[NC13594]折半搜索+二分

题目描述

小L有严重的选择困难症。
早上起床后，需要花很长时间决定今天穿什么出门。
假设一共有k类物品需要搭配选择，每类物品的个数为Ai，每个物品有一个喜欢值Vj，代表小L对这件物品的喜欢程度。
小L想知道，有多少种方案，使得选出来的总喜欢值>M
需要注意，每类物品，至多选择1件，可以不选。

输入描述:

多组输入
每组数据第一行输入k M(k<=6,1<=M<=1e8)，表示有多少类物品
接下来k行，每行以Ai(1<=Ai<=100)开头，表示这类物品有多少个，接下来Ai个数，第j个为Vj(1<=Vj<=1e8),表示小L对这类物品的第j个的喜欢值是多少。

输出描述:

每组输出一行，表示方案数

思路

考虑暴力枚举，共有k类，每类最多100个即有101种选择，那么总共枚举最多 10 1 6 101^6 1016，显然太大了，那么可以考虑折半搜索，那么两部分的次数最多均为 10 1 3 101^3 1013，显然是在可接受的范围内，之后再二分获得每个类别的答案。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7+5;
typedef long long ll;
ll a[N],b[N];
int cnt1,cnt2;
ll k,m;
int cnt[7];
ll v[7][105];

void dfs(ll a[],int &num , int cur,int end ,ll sum)
{
    if(cur == end + 1)
    {
        a[++num] = sum;
        return ;
    }
    for(int i = 0 ; i <= cnt[cur] ; i ++)
        dfs(a,num,cur+1,end,sum + v[cur][i]);
}

int main()
{
    while(~scanf("%lld%lld",&k,&m))
    {
        for(int i = 1 ; i <= k ; i ++)
        {
            scanf("%d",&cnt[i]);
            for(int j = 0 ; j < cnt[i] ; j ++)
                scanf("%lld",&v[i][j]);
            v[i][cnt[i]] = 0;
        }
        int mid = k >> 1;
        cnt1 = cnt2 = 0;
        dfs(a,cnt1,1,mid,0);
        dfs(b,cnt2,mid+1,k,0);
        sort(b+1,b+cnt2+1);
        ll ans = 0;
        for(int i = 1 ; i <= cnt1 ; i ++)
        {
            int pos = upper_bound(b+1,b+cnt2+1,m - a[i]) - b;
            if(pos == cnt2 + 1)
               continue;
            ans += cnt2 - pos + 1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}