pku1742.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 74 行

#include <stdio.h>
#include <algorithm>
#define size 100001
using namespace std;
typedef struct 
{
	int c, n;
} Coin;

Coin c[110], st[size];
bool hv[size];
int M, N;

void Solve()
{
	int i, j, v, n, cnt, max;
	cnt = 0;
	memset(st, 0, sizeof(st[0]) * (M + 1));
	memset(hv, 0, sizeof(hv[0]) * (M + 1));
	for (i = 0, max = 0; i < N; i++)
	{
		max += c[i].c * c[i].n;
	}
	if (max < M)
	{
		M = max;
	}
	hv[0] = 1;
	for (j = 0; j < N; j++)
	{
		v = c[j].c;
		n = c[j].n;
		for (i = 1; i <= M; i++)
		{
			if (!hv[i] && i - v >= 0)
			{
				if (hv[i - v] && !(st[i - v].c == v && st[i - v].n >= n))
				{
					hv[i] = 1;
					cnt++;
					st[i].c = v;
					if (st[i - v].c != v)
					{
						st[i].n = 1;
					}
					else
					{
						st[i].n = st[i - v].n + 1;
					}
				}
			}
		}
	}
	printf("%d\n", cnt);
}

int main()
{
	int i;
	while (scanf("%d %d", &N, &M) != -1 && (M + N))
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &c[i].c);
		}
		for (i = 0; i < N; i++)
		{
			scanf("%d", &c[i].n);
		}
		Solve();
	}
	return 0;
}