题目描述
沼跃鱼通过你的帮助顺利地打开了宝箱,得到了一把"BILIBILI"电击枪。但是沼跃鱼眉头一皱,发现事情并不单纯——宝箱被拿走后房间入口的那块大石板突然变成了山岭巨人。此时沼跃鱼只好拿着刚到手的电击枪迎战了。沼跃鱼使用了“洞悉”技能看穿了山岭巨人的生命值和电击枪的伤害计算方式。电击枪有四个能量槽,每个能量槽都有n种电力输出大小,若四个能量槽分别选择a1,a2,a3,a4的电力输出大小,则总的伤害为a1+a2+a3+a4。注意,每个能量槽最多只能选一种电力输出大小(不选则伤害为0),而总的能量消耗值与总伤害值相等。现在沼跃鱼想知道是否存在一种搭配方式使得电击造成的伤害刚好等于山岭巨人的生命值而不浪费额外的能量。
输入
输入的第一行是一个整数T(0<T≤20),代表接下来有T组数据。
每组数据的第一行有两个整数n,m(0<n<500, m为非负整数),n代表每个能量槽电力输出大小的种数,m代表山岭巨人的生命值。
接下来4行,每行有n个数代表该能量槽可选的电力输出大小。可选的电力输出大小ai满足0≤ai<10^9。
详情参看样例输入。
输出
每组数据输出一行,若存在至少一种搭配方式使总伤害刚好等于山岭巨人的生命值则输出“YES”,否则输出“NO”(不包含双引号)。
样例输入
2
3 16
3 4 5
2 3 4
4 2 3
4 5 6
1 10
1
2
3
11
样例输出
YES
NO
我的程序如下:
#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int t,n,i,j,k,p,flag=0,cg=0;
long long q,m;
int a[600],b[600],c[600],d[600];
cin >> t;
while (t--)
{
cg=0;
flag=0;
cin >> n >> m;
for (i=0;i<n;i++)
{
/*cin >> a[i];*/scanf("%d",&a[i]);
if (a[i]==m)
{
cg=1;
}
}
a[n]=0;
for (i=0;i<n;i++)
{
/*cin >> b[i];*/scanf("%d",&b[i]);
if (b[i]==m)
{
cg=1;
}
}
b[n]=0;
for (i=0;i<n;i++)
{
/*cin >> c[i];*/scanf("%d",&c[i]);
if (c[i]==m)
{
cg=1;
}
}
c[n]=0;
for (i=0;i<n;i++)
{
/*cin >> d[i];*/scanf("%d",&d[i]);
if (d[i]==m)
{
cg=1;
}
}
d[n]=0;
if (cg==1)
{
cout << "YES" << endl;
}
else
{
sort(a,a+n+1);//从小到大排序
sort(b,b+n+1);
sort(c,c+n+1);
sort(d,d+n+1);
/*for (i=0;i<n+1;i++)
{
cout << a[i] << endl;
}*/
for (i=0;(i<n+1)&&flag==0;i++)//四重循环枚举,太耗时了
{
if (a[i]==a[i+1])
{
continue;
}
if (a[i]>m)
{
break;
}
for (j=0;(j<n+1)&&flag==0;j++)
{
if (b[i]==b[i+1])
{
continue;
}
if (b[i]>m)
{
break;
}
for (k=0;(k<n+1)&&flag==0;k++)
{
if (c[i]==c[i+1])
{
continue;
}
if (c[i]>m)
{
break;
}
for (p=0;(p<n+1)&&flag==0;p++)
{
if (d[i]==d[i+1])
{
continue;
}
if (d[i]>m)
{
break;
}
q=a[i]+b[j]+c[k]+d[p];
if (q==m)
{
cout << "YES" << endl;
flag=1;
}
}
}
}
}
if (flag==0)
{
cout << "NO" << endl;
}
}
}
return 0;
}