记录编号	43839	评测结果	AAAAAAAAAA
题目名称	[Vijos 1071] 新年趣事之打牌	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2012-10-14 17:14:26	内存使用	45.21 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

bool written,used[100010];
int w[110],rec[110][100010];

void printit(int deep,int pos)
{
	if (deep==0)
		return;
	if (rec[deep][pos]==-1)
	{
		cout<<"-1\n";
		exit(0);
	}
	else if (rec[deep][pos]==1)
	{
		printit(deep-1,pos-w[deep]);
	}
	else// if(rec[deep][pos]==0)
	{
		printit(deep-1,pos);
		cout<<deep<<' ';
		written=true;
	}
}

int main(void)
{
	freopen("bagb.in","r",stdin);
	freopen("bagb.out","w",stdout);
	int i,j,totalW,n,temp;
	used[0]=true;
	cin>>totalW>>n;
	for (i=1;i<=n;i++)
		cin>>w[i];
	for (i=1;i<=n;i++)
		for (j=totalW;j>=w[i];j--)
		{
			temp=j-w[i];
			if (used[temp])
			{
				if (used[j]==false)
				{
					used[j]=true;
					rec[i][j]=1;
				}
				else
				{
					rec[i][j]=-1;
				}
			}
		}
	if (used[totalW])
	{
		printit(n,totalW);
		if (!written)
			cout<<'0';
		cout<<endl;
	}
	else
	{
		cout<<"0\n";
	}
	return(0);
}