pku2392.cpp

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

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef struct block
{
	int h, c, a;
}Block;

Block b[410];

int hash[41000];
int hashcnt[41000];
int hashid[41000];

bool cmp(const Block &ba, const Block &bb)
{
	return ba.a < bb.a;
}

int main()
{
	int K;
	int i, j;
	int max;
	scanf("%d", &K);
	memset(b, 0, sizeof(b));
	memset(hash, 0, sizeof(hash));
	memset(hashid, -1, sizeof(hashid));
	for (i = 0; i < K; i++)
	{
		scanf("%d %d %d", &b[i].h, &b[i].a, &b[i].c);
		b[i].a -= b[i].h;
	}
	sort(b, b + K, cmp);
	max = 0;
	hash[0] = 1;
	for (i = 0; i < K; i++)
	{
		for (j = 0; j <= b[i].a; j++)
		{
			if (!hash[j] || hash[j + b[i].h])
			{
				continue;
			}
			if (hashid[j] == i && hashcnt[j] >= b[i].c)
			{
				continue;
			}
			hash[j + b[i].h] = 1;
			hashid[j + b[i].h] = i;
			if (hashid[j] == i)
			{
				hashcnt[j + b[i].h] = hashcnt[j] + 1;
			}
			else
			{
				hashcnt[j + b[i].h] = 1;
			}
			if (j + b[i].h > max)
			{
				max = j + b[i].h;
			}
		}
	}
	printf("%d\n", max);
	return 0;
}