4005983_ac_32ms_1376k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 42 行

#include <stdio.h>
#include <string.h>

int c, g;
int pos[20];
int w[20];
int dp[20][15001];

int main()
{
	int i, j, k;

	scanf("%d%d", &c, &g);
	for (i = 0; i < c; i++)
	{
		scanf("%d", &pos[i]);
	}
	for (i = 0; i < g; i++)
	{
		scanf("%d", &w[i]);
	}
	memset(dp, 0, sizeof(dp));
	for (j = 0; j < c; j++)
	{
		dp[0][7500 + w[0] * pos[j]]++;
	}
	for (i = 1; i < g; i++)
	{
		for (j = 0; j < c; j++)
		{
			for (k = 0; k <= 15000; k++)
			{
				int tmp = k - w[i] * pos[j];
				if (tmp < 0 || tmp > 15000)
					continue;
				dp[i][k] += dp[i - 1][tmp];
			}
		}
	}
	printf("%d\n", dp[g - 1][7500]);
	return 0;
}