比赛 |
201712练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
硬币问题 |
最终得分 |
100 |
用户昵称 |
胡嘉兴 |
运行时间 |
0.086 s |
代码语言 |
C++ |
内存使用 |
1.81 MiB |
提交时间 |
2017-12-23 08:02:20 |
显示代码纯文本
#include<cstdio>
#include<vector>
#include<algorithm>
#define M 100 + 7
#define N 100000 + 7
#define INF 99999997
using namespace std;
int v[N], f[N], g[N], h[N];
void print(int* d, int k)
{
while(k)
{
printf("%d ", d[k]);
k -= v[d[k]];
}
puts("");
return;
}
int main()
{
int n, s, ans1, ans2, fs, ft;
freopen("kouka.in", "r", stdin);
freopen("kouka.out", "w", stdout);
scanf("%d%d", &n, &s);
for(int i = 1; i <= n; i++)
{
scanf("%d", &v[i]);
}
for(int j = 1; j <= s; j++)
{
f[j] = -INF;
}
for(int i = 1; i <= s; i++)
{
for(int j = 1; j <= n; j++)
{
if(i >= v[j])
{
if(f[i] < f[i-v[j]]+1)
{
f[i] = f[i-v[g[i]=j]]+1;
}
}
}
}
ans1 = f[s];
for(int i = 1; i <= s; i++)
{
f[i] = INF;
}
for(int i = 1; i <= s; i++)
{
for(int j = 1; j <= n; j++)
{
if(i >= v[j])
{
if(f[i] > f[i-v[j]]+1)
{
f[i] = f[i-v[h[i]=j]]+1;
}
}
}
}
ans2 = f[s];
fs = ft = s;
printf("%d %d\n", ans2, ans1);
print(h, s);
print(g, s);
return 0;
}