BNU29376——沙漠之旅——————【技巧题】

沙漠之旅

Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main

“小胖要穿越一片沙漠,小胖开着一辆大吉普,小胖的吉普油耗高,吉普能放四桶油。”

这就是人人会唱的沙漠之歌~~体现了小胖拔群的聪明才智。

小胖的问题是这样的:现在需要驾车穿越一片沙漠,总的行驶路程为L。小胖的吉普装满油能行驶X距离,同时其后备箱最多能放下四桶油。在起点有N种汽油,每种汽油都有无限桶,一桶能行驶距离Ai。现在小胖想知道:能不能恰好带四桶油,再加上出发前装满的油,使得恰好能行驶L距离。

 

Input

第一行一个正整数T(1 <= T <= 50),表示数据的组数。

接下来T组数据,每组数据的第一行是三个整数L(1 <= L <= 1000),X(1 <= X <= L),N(1 <= N <= 1000)。

接下来N行,每行一个正整数Ai(1 <= Ai <= 1000),表示第i种汽油一桶能行驶的距离。

 

Output

对于每组数据输出一行,若能输出“Yes”,否则输出“No”

 

Sample Input

1
20 9 2
2
3

Sample Output

Yes


#include<bits/stdc++.h>
using namespace std;
int a[2000];
bool flag[2000];
int main(){

    int t;
    scanf("%d",&t);
    while(t--){

        memset(flag,0,sizeof(flag));
        int l,x,n;
        scanf("%d%d%d",&l,&x,&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            flag[a[i]]=1;
        }
        int ans=l-x;
        bool Flag=0;
        sort(a,a+n);
        for(int i=0;i<n;i++){
                if(a[i]>ans)
                    break;
            for(int j=0;j<n;j++){
                if(a[i]+a[j]>ans)
                    break;
                for(int k=0;k<n;k++){
                    if(a[i]+a[j]+a[k]>ans)
                        break;
                    int tmp=ans-a[i]-a[j]-a[k];
                    if(flag[tmp]){

                        Flag=1;
                        break;
                    }
                }
                if(Flag)
                    break;
            }
            if(Flag)
                break;
        }
        if(Flag)
            printf("Yes
");
        else
            printf("No
");
    }
    return 0;
}