比赛 |
201712练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
硬币问题 |
最终得分 |
100 |
用户昵称 |
サイタマ |
运行时间 |
0.021 s |
代码语言 |
C++ |
内存使用 |
0.44 MiB |
提交时间 |
2017-12-22 19:44:32 |
显示代码纯文本
#include<cstdio>
using namespace std;
int read(int &x)
{
bool flags;char ch;
flags=false;
while(ch=getchar(),ch<48 || 57<ch)if(ch=='-')flags=true;
x=ch^'0';
while(ch=getchar(),48<=ch && ch<=57)x=x*10+(ch^'0');
if(flags)return -x;
else return x;
}
int n,s,v[100001],i,j,a[100001],wa[100001],b[100001],wb[100001],s1;
int lyh()
{
freopen("kouka.in","r",stdin);
freopen("kouka.out","w",stdout);
read(n);
read(s);
s1=s;
for(i=1;i<=n;i++)read(v[i]);
for(i=1;i<=100000;i++)a[i]=-1000000,b[i]=1000000;
for(i=1;i<=s;i++)
for(j=1;j<=n;j++)
{
if(i<v[j])continue;
if(a[i]<a[i-v[j]]+1)
{
a[i]=a[i-v[j]]+1;
wa[i]=j;
}
if(b[i]>b[i-v[j]]+1)
{
b[i]=b[i-v[j]]+1;
wb[i]=j;
}
}
printf("%d %d\n",b[s],a[s]);
while(s1>0)
{
printf("%d ",wb[s1]);
s1-=v[wb[s1]];
}
printf("\n");
while(s>0)
{
printf("%d ",wa[s]);
s-=v[wa[s]];
}
return 0;
}
int Main=lyh();
int main(){;}