吃东西
(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<>
对于另外30%的数据n<>
对于100%的数据1<><><><><><>
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[1] y[?] 一个前缀(1~p)
x[2] y[??] 一个前缀(1~pp) pp<>
x[3] y[???] 一个前缀(1~ppp) ppp<>
当一个规模解决不了的时候，分成两半 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++)="">
for (i=1; i<=b; i++)="">
MAX=0;
cnt=cntt=0;
for (i=1; i<=a;>
for (j=1; j<=b;>
if (a[i]+b[j]<>
{
f[a[i]+b[j]]++;
MAX=max(MAX,a[i]+b[j]);
}
for (i=0; i<=max;>
while (f[i])
{
f[i]--;
c[++cnt]=i;
}
for (i=1; i<=c; i++)="">
for (i=1; i<=d; i++)="">
MAX=0;
for (i=1; i<=c;>
for (j=1; j<=d;>
if (aa[i]+bb[j]<>
{
f[aa[i]+bb[j]]++;
MAX=max(MAX,aa[i]+bb[j]);
}
for (i=0; i<=max;>
while (f[i])
{
f[i]--;
cc[++cntt]=i;
}
for (i=cntt; i>=1; i--) if (c[1]+cc[i]<=n)>
now=i;
for (i=1; i<=cnt;>
{
ans+=now;
while (now&& c[i+1]+cc[now]>n) now--;
}
cout<><>
ans=0;
return 0;
}
100分 meet in the middle
联系客服
