吃东西
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个时间，问它有几种吃的方案。
输入格式
第一行5个数分别表示n,A,B,C,D。
第二行A个数分别表示ai。
第三行B个数分别表示bi。
第四行C个数分别表示ci。
第五行D个数分别表示di。
输出格式
一个数表示答案。
输入样例
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。
题解
暴力A*B求出A和B组合的所有方案。
暴力C*D求出C和D组合的所有方案。
再把AB和CD的方案组合。
n太大，不能用sort排序。
因为空间足够大，可以按数值存一个数组，再O(n)从小到大放进去。
因为具有单调性，可以O(n)算出方案数。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int N=100000005,M=5005;
int A,B,C,D,n,maxn,cntab,cntcd,now;
int a[M],b[M],c[M],d[M];
int f[N],ab[M*M],cd[M*M];
LL ans;
int main(){
scanf("%d%d%d%d%d",&n,&A,&B,&C,&D);
for(int i=1;i<=A;i++)scanf("%d",&a[i]);
for(int i=1;i<=B;i++)scanf("%d",&b[i]);
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
if(a[i]+b[j]<=n){
f[a[i]+b[j]]++;
maxn=max(maxn,a[i]+b[j]);
}
for(int i=0;i<=maxn;i++)
while(f[i]){
f[i]--;
ab[++cntab]=i;
}
for(int i=1;i<=C;i++)scanf("%d",&c[i]);
for(int i=1;i<=D;i++)scanf("%d",&d[i]);
maxn=0;
for(int i=1;i<=C;i++)
for(int j=1;j<=D;j++)
if(c[i]+d[j]<=n){
f[c[i]+d[j]]++;
maxn=max(maxn,c[i]+d[j]);
}
for(int i=0;i<=maxn;i++)
while(f[i]){
f[i]--;
cd[++cntcd]=i;
}
for(int i=cntcd;i>=1;i--)
if(ab[1]+cd[i]<=n){
now=i;
break;
}
for(int i=1;i<=cntab;i++){
ans+=now;
while(now&&ab[i+1]+cd[now]>n)now--;
}
printf("%lld
",ans);
return 0;
}