# 14029: 【原4029】shop

### 题目描述

author: Kodak 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4029 ﻿

## Description

Kodak开了一家小店赚外快，因为店小，所以只有n种不同价格的商品卖，不过好在批发商给力，货源充足，所以每种商品都有无限件

## Sample Input

``````3
24 48 100
4
0
520
1024
1314
``````

## Sample Output

``````YES
YES
YES
NO
``````

## Pangbo13's solution

``````#include<stack>
#include<iostream>
using namespace std;
#define Inf 0x3f3f3f3f

int main(){
int N,M,mod,*a,*min;
bool* done;
stack<int> buffer;
scanf("%d",&N);
a = new int[N];
for(int i = 0;i<N;i++) scanf("%d",&a[i]);
mod = a[0];
min = new int[mod];
done = new bool[mod];
for(int i = 0;i<mod;i++){
done[i] = 0;
min[i] = Inf;
}
min[0]=0;
buffer.push(0);
while(buffer.size()){
int x=buffer.top();
buffer.pop();
if(done[x]) continue;
done[x]=1;
for(int i=1;i<N;i++){
int y=(x+a[i])%mod;
if(min[y]>min[x]+a[i]){
min[y]=min[x]+a[i];
done[y] = 0;
buffer.push(y);
}
}
}
scanf("%d",&M);
int aim;
for(int i=0;i<M;i++){
scanf("%d",&aim);
if(aim>=min[aim%mod]) printf("YES\n");
else printf("NO\n");
}
}
``````

## q4x3's solution

``````/**
* 最短路 spfa算法
* 答案数组中dis[k]存储mod m余k的数中可以被凑出的最小总价
**/
#include <iostream>
#include <stdio.h>

using namespace std;

int N, a[1010], M, ask[300233], dis[20233], m = 20233, INF = 41000000, que[10100000];
bool vis[20233]; //访问标记 是否在队中

void spfa() {
int head = 0, rear = 0;
for(int i = 1;i < m;++ i)
dis[i] = INF;
que[head] = 0; ++ rear;
//队空则结束循环
while(head < rear) {
//记录队首
int cur = que[head];
//队首出队
vis[que[head]] = 0;
++ head;
//计算每条边可以到达的节点及路径长度 若短于记录 则更新记录 若vis为0 则入队
for(int i = 0;i < N;++ i) {
//计算
int node = (cur + a[i]) % m;
int tmpdis = dis[cur] + a[i];
//判断
if(tmpdis < dis[node]) {
//更新
dis[node] = tmpdis;
//入队
if(vis[node] == 0) {
que[rear] = node;
++ rear;
vis[node] = 1;
}
}
}
}
}

int main() {
cin >> N;
for(int i = 0;i < N;++ i) {
scanf("%d", &a[i]);
if(a[i] < m) m = a[i];
}
spfa();
cin >> M;
for(int i = 0;i < M;++ i) {
scanf("%d", &ask[i]);
}
for(int i = 0;i < M;++ i) {
if(dis[ask[i] % m] <= ask[i]) printf("YES\n");
else printf("NO\n");
}
}
``````

## zqy2018's solution

``````/*
Hint: use infinite knapsack (the test data is much smaller than you thought)
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m, a[1005], ans[300005], maxi = 0;
bool vis[40000005] = {0};
void init(){
n = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
m = read();
for (int i = 1; i <= m; ++i)
ans[i] = read(), maxi = max(maxi, ans[i]);
vis[0] = true;
for (int i = 1; i <= n; ++i){
int t = a[i];
for (int j = t; j <= maxi; ++j)
vis[j] = vis[j] || vis[j - t];
}
}
void solve(){
for (int i = 1; i <= m; ++i){
if (vis[ans[i]])
printf("YES\n");
else
printf("NO\n");
}
}
int main(){
init();
solve();
return 0;
}
``````