# 11069: 【原1069】二哥的硬币

### 题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1069

## 说明

http://poj.org/problem?id=1742

## Sample Input

2 5
1 4 2 1
3 10
1 2 4 2 1 1
0 0


## Sample Output

4
8


## FineArtz's solution

/* 二哥的硬币 */
#include <iostream>
#include <cstring>
using namespace std;

int a[100005], c[1005], f[100005];

void work(int n, int m){
memset(a, 0, sizeof(a));
memset(c, 0, sizeof(c));
memset(f, -1, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
for (int i = 1; i <= n; ++i)
cin >> c[i];
for (int i = 1; i <= n; ++i){
for (int j = 0; j <= m; ++j){
if (f[j] >= 0)
f[j] = c[i];
else if (j < a[i] || f[j - a[i]] < 0)
f[j] = -1;
else
f[j] = f[j - a[i]] - 1;
}
}
int ans = 0;
for (int i = 1; i <= m; ++i)
if (f[i] >= 0)
++ans;
cout << ans << '\n';
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
while (n != 0 || m != 0){
work(n, m);
cin >> n >> m;
}
return 0;
}


## yyong119's solution

#include <cstdio>
#include <cstring>
#define MAX_N 105
#define MAX_M 100005
using namespace std;

int n, m;
int w[MAX_N], c[MAX_N], sum[MAX_M], f[MAX_M];

int main() {

while (~scanf("%d%d", &n, &m)) {

if (n == 0 && m == 0)
break;
for (int i = 0; i < n; ++i)
scanf("%d", &w[i]);
for (int i = 0; i < n; ++i)
scanf("%d", &c[i]);

memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 0; i < n; ++i) {
memset(sum,0,sizeof(sum));
for (int j = w[i]; j <= m; ++j)
if(!f[j] && f[j - w[i]] && sum[j - w[i]] < c[i]) {
f[j] = 1;
sum[j] = sum[j - w[i]] + 1;
}
}
int ans = 0;
for (int i = 1; i <= m; ++i)
if (f[i])
++ans;
printf("%d\n", ans);
}
return 0;
}