记录编号	47452	评测结果	AAAAAAAAAA
题目名称	硬币问题	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2012-11-01 17:51:54	内存使用	2.20 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100000 + 10, INF = 0x7ffffff;
int n, m, v[N];
int f[N], g[N], a[N], b[N];
void print(int* d, int k) {
    while(k) {
        printf("%d ", d[k]);
        k -= v[d[k]];
    } printf("\n");
}
int main() {
    freopen("kouka.in", "r", stdin);
    freopen("kouka.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", v+i);
    fill(f, f+m+1, INF);
    fill(g, g+m+1, -INF);
    f[0] = g[0] = 0;
    for(int i=1; i<=m; 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[a[i] = j]] + 1;
                if(g[i] < g[i - v[j]] + 1)
                    g[i] = g[i - v[b[i] = j]] + 1;
            }
    printf("%d %d\n", f[m], g[m]);
    print(a, m);
    print(b, m);
    return 0;
}