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

沙漠之旅

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld      Java class name: Main

Submit Status

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

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

小胖的问题是这样的：现在需要驾车穿越一片沙漠，总的行驶路程为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\n");

        else

            printf("No\n");

    }

    return 0;

}