变态背包问题

原题链接:Hit

#include <iostream>
#include <cstring>
#include <algorithm>
const int	maxn = 100000;
int		dp[maxn];
int		a[maxn];
using namespace std;

struct BG
{
	int h, l, t;
} bg[31];

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


int main()
{
	int n, maxh, tmax;
	while ( cin >> n, n >= 0 )
	{
		maxh = 0;
		for ( int i = 0; i < n; i++ )
		{
			cin >> bg[i].h >> bg[i].l >> bg[i].t;
			tmax = max( tmax, bg[i].t );    /* 求得最长时间 */
		}
		fill( dp, dp + maxn, 0 );
		sort( bg, bg + n, cmp );                /*按bg的发起人离开时间升序排列 */
		for ( int i = 0; i < n; i++ )
			for ( int j = tmax; j >= bg[i].l; j-- )
				if ( j <= bg[i].t )     /* bg必须在主人离开前结束 */
				{
					dp[j]	= max( dp[j], dp[j - bg[i].l] + bg[i].h );
					maxh	= max( maxh, dp[j] );
				}

		cout << maxh << endl;
	}
	return(0);
}

 

0

发表评论

邮箱地址不会被公开。 必填项已用*标注