2392.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"vector"
#include"algorithm"
using namespace std;

struct block
{
	int h,a,c;
}b[400];
bool reach[40001];
int use[40001];
int kind[40001];
int n;
vector<int> q;

bool cmp(block a,block b)
{
	return a.a<b.a;
}

void init()
{
	int i;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>b[i].h>>b[i].a>>b[i].c;

	sort(b,b+n,cmp);
}

void doit()
{
	int i,r,t,k,s;
	for(i=1;i<=b[n-1].a;i++)
		reach[i]=0,kind[i]=-1;

	reach[0]=1;
	
	q.push_back(0);

	for(i=0;i<n;i++)
	{
		s=b[i].a-b[i].h;
		for(k=0;k<q.size();k++)
		{
			r=q[k];
			if(r<=s&&(kind[r]!=i||use[r]<b[i].c)&&!reach[(t=r+b[i].h)] )
			{
				reach[t]=1;
				
				kind[t]=i;

				if(kind[r]!=i)use[t]=1;
				else use[t]=use[r]+1;

				q.push_back(t);
			}
		}
	}

	for(i=b[n-1].a;i;i--)
		if(reach[i])break;
	cout<<i<<endl;
}

int main()
{
	init();
	doit();
	return 0;
}