11295: 【原1295】nuggets

题目

题目描述

author: Xutong Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1295

Description

大一鸣正在和主任大魔王进行斗争，他们选择用卡牌游戏决一胜负，这种卡牌很特殊，有N种牌，每种牌面的数字分别不同，但每种牌的数量无限。胜利规则是，给定一组牌，问是否存在这组牌无法加出来的数字。（例如N=3，牌组为面值为3、面值为6、面值为10的三张牌，则你不可能加出1、2、4、5等数字，而可以加出3、6、9、12等数字）如果有的话进一步问最大的无法加出来的数字是多少，请帮助帮助大一鸣获得胜利。

Input Format

第一行：牌组的种类数N（1<=N<=10）

第二行到第N+1行：每种牌的数值(1<=Ai<=256)

Output Format

只有一行：不能加出的最大数字或0（所有数字都能加出来或者能加出来的数字没有上限）

Sample Input

3
3
6
10

Sample Output

17

Hint

答案不超过100000

yyong119's solution

#include <cstdio>
#define MAX_T 1010000
#define MAX_N 15
using namespace std;

bool possible[MAX_T];
int card[MAX_N], n;

int main(){
    scanf("%d", &n);
    for (register int i = 0; i < n; ++i) {
        scanf("%d", &card[i]);
        if (card[i] == 1) {
            printf("0\n");
            return 0;
        }
        possible[card[i]] = 1;
    }
    for (register int i = 0; i < MAX_T; ++i)
        if (possible[i])
            for (register int j = 0; j < n; ++j)
                possible[i + card[j]] = 1;
    register int i;
    for (i = 1000000 ;possible[i]; --i);
    if (i > 100000) printf("0\n");
    else printf("%d\n", i);
    return 0;
}