比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 硬币问题 最终得分 100
用户昵称 Ceres 运行时间 0.063 s
代码语言 C++ 内存使用 1.08 MiB
提交时间 2017-12-25 13:12:41
显示代码纯文本
#include <iostream>
#include <cstdio>
#define INF 0x7fffffff
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
int n=0,s=0,v[110]={0};
int fax[100010]={0},fin[100010]={0};
void ansn(int S)
{
	for(int i=1;i<=n;i++)
		if(v[i]<=S && fin[S]==fin[S-v[i]]+1)
		{
			cout<<i<<' ';
			ansn(S-v[i]);
			return;
		}
}
void ansx(int S)
{
	for(int i=1;i<=n;i++)
		if(v[i]<=S && fax[S]==fax[S-v[i]]+1)
		{
			cout<<i<<' ';
			ansx(S-v[i]);
			return;
		}
}
int main()
{
	freopen("kouka.in","r",stdin);
	freopen("kouka.out","w",stdout);
	cin>>n>>s;
	for(int i=1;i<=n;i++)
		cin>>v[i];
	for(int i=1;i<=s;i++)
	{
		fax[i]=-INF;
		fin[i]=INF;
	}
	for(int i=1;i<=n;i++)
		for(int j=v[i];j<=s;j++)
		{
			fax[j]=max(fax[j],fax[j-v[i]]+1);
			fin[j]=min(fin[j],fin[j-v[i]]+1);
		}
	if(fin[s]==INF)
		cout<<"-1"<<endl;
	else
	{
		cout<<fin[s]<<' '<<fax[s]<<endl;
		ansn(s);
		cout<<endl;
		ansx(s);
		cout<<endl;
	}
	return 0;
}