B. 沙漠之旅（分组背包）

全栈程序员站长

发布于 2022-01-21 08:15:21

1580

发布于 2022-01-21 08:15:21

大家好，又见面了，我是全栈君。

B. 沙漠之旅

 Time Limit: 1000ms   
 Case Time Limit: 1000ms   
 Memory Limit: 65536KB   
    64-bit integer IO format: 
 %lld      Java class name: 
 Main 
 Submit 
 Status 
 PID: 29376 
 Font Size: 
  +  
  –

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

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

小胖的问题是这种：如今须要驾车穿越一片沙漠，总的行驶路程为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

Sample Output

Yes

#include<stdio.h>
#include<string.h>
int flag[5][1005];
int main()
{
    int t,l,x,n,d,sum;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&l,&x,&n);
        l-=x; sum=0;
        memset(flag,0,sizeof(flag));
        flag[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&d);
            for(int j=1;j<=4;j++)
            for(int e=d;e<=l;e++)
            if(flag[j-1][e-d])
            flag[j][e]=1;
        }
        if(flag[4][l])
        printf("Yes\n");
        else printf("No\n");

    }
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116474.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java