记录编号	162750	评测结果	AAAAAAAAAA
题目名称	[Vijos 1071] 新年趣事之打牌	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-05-20 08:07:06	内存使用	7.98 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
int m,n,w[10000],opt[1000000],path[1000000];
int main()
{
	freopen("bagb.in","r",stdin);
	freopen("bagb.out","w",stdout);
	scanf("%d",&m);
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	 scanf("%d",&w[i]);
	opt[0]=1;
    for (int i=1;i<=n;++i)
     for (int j=m;j>=w[i];--j)
     {
      if (opt[j-w[i]])
       if (path[j]==0) path[j]=i;
      opt[j]+=opt[j-w[i]];
     }
    if (opt[m]>1)
    {
    	cout<<-1;
    	return 0;
    }
    else if (opt[m]==0)
    {
    	cout<<0;
    	return 0;
    }
    else 
    {
    	int f[10000]={0};
    	int x=path[m];
    	while (x>0)
    	{
    		f[x]=1;
    		m-=w[x];
    		x=path[m];
    	}
    	for (int i=1;i<=n;++i)
    	 if (f[i]==0) cout<<i<<" ";
    	return 0;
    }
}