清北学堂模拟赛d2t5 吃东西(eat)

题目描述
一个神秘的村庄里有4家美食店。这四家店分别有A,B,C,D种不同的美食。LYK想在每一家店都吃其中一种美食。每种美食需要吃的时间可能是不一样的。
现在给定第1家店A种不同的美食所需要吃的时间a1,a2,…,aA。
给定第2家店B种不同的美食所需要吃的时间b1,b2,…,bB。
以及c和d。
LYK拥有n个时间，问它有几种吃的方案。

输入格式(eat.in)
第一行5个数分别表示n,A,B,C,D。
第二行A个数分别表示ai。
第三行B个数分别表示bi。
第四行C个数分别表示ci。
第五行D个数分别表示di。

输出格式(eat.out)
一个数表示答案。

输入样例
11 3 1 1 1
4 5 6
3
2
1

输出样例
2

对于30%的数据A,B,C,D<=50
对于另外30%的数据n<=1000。
对于100%的数据1<=n<=100000000，1<=A,B,C,D<=5000,0<=ai,bi,ci,di<=100000000。

分析：这道题刚开始想着用dp，但是这数据明显不可做啊，状态都开不下.其实对枚举优化一下就好了......

试考虑最暴力的做法，四重循环枚举ABCD.对于四重循环有一个常用的优化就是利用前3个数就能算出第4个数，在这道题中如果我们知道了A+B,就可以知道C+D的具体范围，那么把C+D的所有取值排序，找到第一个A+B + C+D>n的C+D的位置i,那么ans += (i - 1),所以做法就是先枚举出所有的A+B的组合，再枚举出所有C+D的组合，排个序，枚举A+B然后查找C+D的位置累加答案即可.

一个复杂度很高的枚举，如果我们能够折半搜索，复杂度就会降低很多，要熟记这些优化.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, A, B, C, D, a[], b[], c[], d[],maxn,cur;

int f[], c1[], c2[],cnt1,cnt2;

long long ans = ;

int main()

{

    scanf("%d%d%d%d%d", &n, &A, &B, &C, &D);

    for (int i = ; i <= A; i++)

        scanf("%d", &a[i]);

    for (int i = ; i <= B; i++)

        scanf("%d", &b[i]);

    for (int i = ; i <= C; i++)

        scanf("%d", &c[i]);

    for (int i = ; i <= D; i++)

        scanf("%d", &d[i]);

    for (int i = ; i <= A; i++)

        for (int j = ; j <= B; j++)

            if (a[i] + b[j] <= n)

            {

                f[a[i] + b[j]]++;

                maxn = max(maxn, a[i] + b[j]);

            }

    for (int i = ; i <= maxn; i++)

        while (f[i])

        {

            f[i]--;

            c1[++cnt1] = i;

        }

    maxn = ;

    for (int i = ; i <= C; i++)

        for (int j = ; j <= D; j++)

            if (c[i] + d[j] <= n)

            {

                f[c[i] + d[j]]++;

                maxn = max(maxn, c[i] + d[j]);

            }

    for (int i = ; i <= maxn; i++)

        while (f[i])

        {

            f[i]--;

            c2[++cnt2] = i;

        }

    for (cur = cnt2; cur >= ; cur--)

        if (c1[] + c2[cur] <= n)

            break;

    for (int i = ; i <= cnt1; i++)

    {

        ans += cur;

        while (cur && c1[i + ] + c2[cur] > n)

            cur--;

    }

    printf("%lld\n", ans);

    return ;

}