3129555_ac_907ms_1420k.cc

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

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

using namespace std;

struct node
{
	int a, c;
}coin[101];

int a[100001], b[100001][2];

bool cmp(node a,node b)
{
	if(a.a < b.a) 
	{
		return true;
	}
	else
	{
		if(a.a==b.a&&a.c>b.c)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

int main() 
{
	int n, m, i, j, sum, max, all;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(m==0&&n==0)
		{
			break;
		}
		memset(b,-1,sizeof(b));
		memset(a,0,sizeof(a));
		a[0] = 1;
		for(i = 0; i < n; i++)
		{
			scanf("%d",&coin[i].a);
		}
		max = 0; sum = 0; all = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%d",&coin[i].c);
		}
		sort(coin,coin+n,cmp);
		for(j = 0; j < n; j++)
		{
			all += coin[j].a*coin[j].c;
			if(all>m) 
			{
				all = m;
			}
			for(i = coin[j].a; i <= all; i++)
			{
				if(a[i])
				{
					continue;
				}
				int temp = i - coin[j].a;
				if(a[temp]==0)
				{
					continue;
				}
				if(b[temp][0]==j&&b[temp][1]>=coin[j].c)
				{
					continue;
				}
				b[i][0] = j;
				if(b[temp][0]==j)
					b[i][1]=b[temp][1]+1;
				else 
					b[i][1]=1;
				a[i] = 1;
				sum++;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}