1337.txt

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

#include"stdio.h"

int ans[300];
int a[100],d[100],t[100];

int main()
{
	int cas, i, j, n, temp;
	bool key;

	scanf( "%d", &cas );

	while( cas-- )
	{
		scanf( "%d", &n );
		for( i=0; i<n; i++ )
		scanf( "%d %d %d", &t[i], &a[i], &d[i] );
		
		for( i=0; i<=250; i++ )
			ans[i] = 0;

		for( i=249; i>=0; i-- )
		{
			key = true;ans[i] = 99999999;
			for( j=0; j<n; j++ )
			{
				if( a[j] <= i && i+t[j] <= d[j] && ( temp = ans[i+t[j]] + t[j] ) < ans[i] )
				ans[i] = temp, key = false;
			}
			if( key ) ans[i] = ans[i+1];
			
		}
		printf( "%d\n", ans[0] );
	}

	return 0;
}