比赛 |
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;
}