记录编号	521859	评测结果	AAAAAAAAAA
题目名称	硬币问题	最终得分	100
用户昵称	李宴彬	是否通过	通过
代码语言	C++	运行时间	0.110 s
提交时间	2018-11-07 22:55:48	内存使用	5.06 MiB

#include <bits/stdc++.h> 
using namespace std;
int mina[100010],maxb[100010];
int jla[100010],jlb[100010];
int yb[100010];
int n,s;
int main()
{
	freopen("kouka.in","r",stdin);
	freopen("kouka.out","w",stdout);
	for (int i=1;i<=100010;i++) mina[i]=1000010,maxb[i]=-1000010;
	cin>>n>>s;
	for (int i=1;i<=n;i++) cin>>yb[i];
	for (int i=1;i<=s;i++)
	  for (int j=1;j<=n;j++)
	  {
	  	 if (i<yb[j]) continue;
		  if (mina[i]>mina[i-yb[j]]+1)
	  	  {
	  	  	mina[i]=mina[i-yb[j]]+1;
	  	  	jla[i]=j;
			}
		if (maxb[i]<maxb[i-yb[j]]+1)	
		{
			maxb[i]=maxb[i-yb[j]]+1;
			jlb[i]=j;
		}
	  }
	  cout<<mina[s]<<" "<<maxb[s]<<endl;
	  int t=s;
	  while(t)
	  {
	  	 cout<<jla[t]<<" ";
	  	 t-=yb[jla[t]];
	  }
	  cout<<endl;
	  while(s)
	  {
	  	cout<<jlb[s]<<" ";
	  	s-=yb[jlb[s]];
	  }
	  cout<<endl;
	  return 0;
}