记录编号 163942 评测结果 AAAAAAAAAA
题目名称 [Vijos 1071] 新年趣事之打牌 最终得分 100
用户昵称 Gravatar啊吧啦吧啦吧 是否通过 通过
代码语言 C++ 运行时间 0.005 s
提交时间 2015-05-27 10:56:18 内存使用 1.08 MiB
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <fstream>
#define cin fin
#define cout fout
 
using namespace std;
 
const int MAXN = 101;
ifstream fin("bagb.in");
ofstream fout("bagb.out");
int totalw, w[MAXN], n, tot = 0, f[100001], zhao[100001];
bool pd[MAXN] = {0};
 
/*bool cmp(int a, int b)
{
    return a > b;
}*/
 
/*bool findcard(int ac, int x)
{
    for(int i = ac; i <= n; i ++)
    {
        if(w[i] == x)
        {
            pd[i] = 1;
            return 1;
        }
        else if(w[i] < x)
        {
            if(findcard(i + 1, x - w[i]))
            {
                pd[i] = 1;
                return 1;
            }
            else
                continue;
        }
    }
    return 0; 
}
*/
int main()
{
    ios::sync_with_stdio(false);
    cin >> totalw >> n;
    for(int i = 1; i <= n; i ++)
        cin >> w[i];
    for(int i = 1; i <= totalw; i ++)
        f[i] = 0;
    f[0] = 1;
//  sort(w + 1, w + n + 1, cmp);
     
    for(int i = 1; i <= n; i ++)
        for(int j = totalw; j >= w[i]; j --)
        {
            if(f[j - w[i]] == 1 && f[j] == 0)
                zhao[j] = i;
            f[j] += f[j - w[i]];
        } 
    if(f[totalw] == 0)
        cout << 0 << endl;
    else if(f[totalw] > 1)
        cout << -1 << endl;
    else
    {
        /*findcard(1, totalw);
        bool first = 1;
        for(int i = 1; i <= n; i ++)
            if(! pd[i])
            {
                if(first)
                    first = 0;
                else
                    cout << ' ';
                cout << i;
            }
        cout << '\n';*/
        int a = totalw, b;
        while(zhao[a] != 0)
        {
            b = w[zhao[a]];
            w[zhao[a]] = 0;
            a -= b;
        }
        for(int i = 1; i <= n; i ++)
            if(w[i] != 0)
                cout << i << ' ';
    }
//  system("pause");
    return 0;
}