14029: 【原4029】shop

题目

题目描述

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

Description

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

因为各种原因，有时候顾客会对购买的总价有特殊的要求，比如计算机科学家泰玛仕一定要总价1024，给小姐姐买礼物的面包需要总价520或者1314，或者纯粹来找茬的张三要买0元商品

但是Kodak店里不一定有1元的商品，所以并不是所有价格都凑得出来，所以他需要一个程序解决能知道某一个总价能否凑出

Input Format

第一行一个数N, N <= 1000

第二行N个数ai，为N件商品的价格，ai <= 20000

第三行一个数M，有特殊要求的顾客个数， M <= 300000

之后M行，每行一个数bi，为该顾客要求的总价数，bi <= 40000000

Output Format

对个顾客的要求输出一行，如果能凑出要求的总价，输出YES，否则输出NO

Sample Input

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;
}