4024954_ac_2313ms_1024k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int num[100001][2];
int a[10000];
int n, m;

int main()
{
	int i, j;

	while (1)
	{
		scanf("%d%d", &n, &m);
		if (n == 0)
			break;
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		memset(num, 0, sizeof(num));
		num[0][0] = 1;num[0][1] = 0;
		for (i = 0; i < n; i++)
		{
			for (j = m - a[i]; j >= 0; j--)
			{
				if (num[j][0])
				{
					num[j + a[i]][1] = 1;
				}
				if (num[j][1])
				{
					num[j + a[i]][0] = 1;
				}
			}
		}
		int ans = 0;
		for (i = 1; i <= m; i++)
		{
			if (num[i][1] && !num[i][0])
				ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}