记录编号	47571	评测结果	AAAAAAAAAA
题目名称	硬币问题	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.268 s
提交时间	2012-11-02 07:48:10	内存使用	4.40 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int a[110],minused[110],maxused[110],get[100010],rec[100010],which[100010];
bool f[100010];

void findway(int i,int* used)
{
	while (i)
	{
		used[which[i]]++;
		i-=rec[i];
	}
}

int main(void)
{
	freopen("kouka.in","r",stdin);
	freopen("kouka.out","w",stdout);
	int i,j,n,s,minget,maxget;
	cin>>n>>s;
	for (i=1;i<=n;i++)
		cin>>a[i];
	f[0]=true;
	get[0]=0;
	for (i=1;i<=s;i++)
	{
		for (j=1;j<=n;j++)
		{
			if (i-a[j]<0)
				continue;
			if (f[i-a[j]])
			{
				if (!f[i])
				{
					f[i]=true;
					get[i]=get[i-a[j]]+1;
					rec[i]=a[j];
					which[i]=j;
				}
				else
				{
					if (get[i]>get[i-a[j]]+1)
					{
						get[i]=get[i-a[j]]+1;
						rec[i]=a[j];
						which[i]=j;
					}
				}
			}
		}
	}
	if (!f[s])
	{
		cout<<"-1\n";
		return(0);
	}
	minget=get[s];
	findway(s,minused);
	memset(f,0,sizeof(f));
	memset(get,0,sizeof(get));
	f[0]=true;
	get[0]=0;
	for (i=1;i<=s;i++)
	{
		for (j=1;j<=n;j++)
		{
			if (i-a[j]<0)
				continue;
			if (f[i-a[j]])
			{
				if (!f[i])
				{
					f[i]=true;
					get[i]=get[i-a[j]]+1;
					rec[i]=a[j];
					which[i]=j;
				}
				else
				{
					if (get[i]<get[i-a[j]]+1)
					{
						get[i]=get[i-a[j]]+1;
						rec[i]=a[j];
						which[i]=j;
					}
				}
			}
		}
	}
	maxget=get[s];
	findway(s,maxused);
	cout<<minget<<' '<<maxget<<endl;
	s=0;
	for (i=1;i<=n;i++)
		while (minused[i])
		{
			minused[i]--;
			if (s)
			{
				cout<<' '<<i;
			}
			else
			{
				s=1;
				cout<<i;
			}
		}
	cout<<endl;
	s=0;
	for (i=1;i<=n;i++)
		while (maxused[i])
		{
			maxused[i]--;
			if (s)
			{
				cout<<' '<<i;
			}
			else
			{
				s=1;
				cout<<i;
			}
		}
	cout<<endl;
	return(0);
}