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