题目

吃东西

吃东西

(eat)

Time Limit:2000ms   Memory Limit:1024MB

题目描述

一个神秘的村庄里有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。

AC代码

/*

    1024MB*1024*1024/4 = 225000000个int数组

    A和B   C和D

    A和B和C和D

    A和B中的一种   C和D的一种

    A和B  双重循环  来得到一个f[i]表示花了i这个时间有几种可能  A*B

    进行桶排序，把f按次序的放进x数组中，A*B种可能排个序

    C和D  双重循环  来得到一个g[i]表示花了i这个时间有几种可能  C*D 

    进行桶排序，把g按次序的放进y数组中，C*D种可能排个序

    A*B 一个数组x   C*D的一个数组y   查询存在多少对i,j，使得x[i]+y[j]<=n  （x和y都是有序的）

    x和y都是顺序的。

    x[1]  y[?]  一个前缀(1~p) 

    x[2]  y[??]  一个前缀(1~pp)  pp<=p

    x[3]  y[???] 一个前缀(1~ppp)  ppp<=pp

    当一个规模解决不了的时候，分成两半  meet in the middle

*/

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int f[100000005],c[25000005],cc[25000005];

int A,B,C,D,n,a[5005],b[5005],aa[5005],bb[5005],MAX,cnt,cntt,i,j,now;

long long ans;

int main()

{

    freopen("eat.in","r",stdin);

    freopen("eat.out","w",stdout);

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

    if (n==0 && A==0 && B==0 && C==0 && D==0) return 0;

    for (i=1; i<=A; i++) scanf("%d",&a[i]);

    for (i=1; i<=B; i++) scanf("%d",&b[i]);

    MAX=0;

    cnt=cntt=0;

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

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

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

            {

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

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

            }

    for (i=0; i<=MAX; i++)

    while (f[i])

        {

            f[i]--;

            c[++cnt]=i;

        }

    for (i=1; i<=C; i++) scanf("%d",&aa[i]);

    for (i=1; i<=D; i++) scanf("%d",&bb[i]);

    MAX=0;

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

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

            if (aa[i]+bb[j]<=n)

            {

                f[aa[i]+bb[j]]++;

                MAX=max(MAX,aa[i]+bb[j]);

            }

    for (i=0; i<=MAX; i++)

    while (f[i])

        {

            f[i]--;

            cc[++cntt]=i;

        }

    for (i=cntt; i>=1; i--) if (c[1]+cc[i]<=n) break;

    now=i;

    for (i=1; i<=cnt; i++)

    {

        ans+=now;

        while (now&& c[i+1]+cc[now]>n) now--;

    }

    cout<<ans<<endl;< p="">

    ans=0;

    return 0;

}

100分 meet in the middle

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com