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

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

1
20 9 2
2
3

Sample Output

Yes

#include
#include
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");

    }
}