절강대학 2008 년 대학원 재시험 기 시험 5 번

졸업
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1918    Accepted Submission(s): 707
Problem Description
매년 졸업 하 는 계절 에 많은 졸업생 들 이 미 친 듯 이 기뻐한다. 친 한 친구 들 이 단체 식 사 를 약속 하 는데 인터넷 에 서 는 'bg' 라 고 부른다.서로 다른 단체 에 참가 하 는 bg 는 서로 다른 느낌 을 가 질 수 있 습 니 다. 우 리 는 하나의 비 마이너스 정수 로 모든 bg 에 '즐거움 도' 를 정의 할 수 있 습 니 다.현재 bg 목록 을 지정 합 니 다. 위 에 모든 bg 의 즐거움, 지속 길이, bg 발기인 의 출 교 시간 을 보 여 줍 니 다. 일련의 bg 시간 을 배정 하여 자신 이 가장 큰 즐거움 을 얻 을 수 있 도록 하 십시오.
예 를 들 어 bg 가 4 번 있 습 니 다.
1 차 즐거움 은 5 로 1 시간 지속 되 며 발기인 은 1 시간 후에 떠 나 야 한다.
2 차 즐거움 은 10 으로 2 시간 지속 되 며 발기인 은 3 시간 후에 떠 나 야 한다.
3 차 즐거움 은 6 으로 1 시간 지속 되 며 발기인 은 2 시간 후에 떠 나 야 한다.
4 차 즐거움 은 3 으로 1 시간 지속 되 며 발기인 은 1 시간 후에 떠 나 야 한다.
가장 큰 즐거움 을 얻 는 안 배 는 3 차 전 을 먼저 시작 하고 즐거움 을 얻 는 것 이다. 6. 1 시간 에 끝나 면 발기인 도 떠 날 수 있다.2 차 전 을 시작 해 즐거움 10 을 얻 고 3 시간 만 에 발기인 이 떠 날 수 있 었 다.발기인 들 이 학 교 를 떠 났 기 때문에 다른 bg 를 더 이상 배정 할 수 없습니다.그래서 얻 은 최대 즐거움 은 16 이다.
bg 는 발기인 이 떠 나 기 전에 끝내 야 합 니 다. 중간 에 bg 를 떠 나 서 는 안 되 고 중간 에 bg 를 가입 해 서 는 안 됩 니 다.
또 당신 의 인 맥 이 너무 좋아 서 30 개 단체 bg 에 이 를 수 있 으 므 로 이 시간 안배 문 제 를 해결 하기 위해 프로그램 을 써 야 합 니 다.
Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 하나의 정수 N (< = 30) 을 포함 하고 그 다음 에 N 줄 이 있 으 며 줄 마다 bg 의 정 보 를 제공 합 니 다.
h l t
그 중에서 h 는 즐거움 도 이 고 l 은 지속 시간 (시간) 이 며 t 는 발기인 이 학 교 를 떠 나 는 시간 이다.데이터 보증 l 은 t 보다 크 지 않 습 니 다. 발기인 이 t 시간 후에 떠 나 야 한다 면 bg 는 주인 이 떠 나 기 전에 끝내 야 합 니 다.
N 이 마이너스 일 때 입력 이 끝 납 니 다.
 
Output
모든 테스트 용례 의 출력 은 한 줄 을 차지 하고 출력의 최대 즐거움 을 차지한다.
Sample Input

3
6 3 3
3 2 2
4 1 3
4
5 1 1
10 2 3
6 1 2
3 1 1
-1

Sample Output

7
16

    ：

      ，  ，

       ，      ，

             ，  

#include
using namespace std;

typedef struct{
	int hd;//   
	int lst;//    
	int lvt;//    
}bg;

const int NMAX = 31;

bg B[NMAX];
int N;
int m[NMAX][1000];

//        
int cmp(const void*A,const void*B)
{
	return ((bg*)A)->lvt - ((bg*)B)->lvt;
}

int dp()
{
	qsort(B,N,sizeof(bg),cmp);
	int mlvt = B[N-1].lvt;//      ，       

	int i,j;
	memset(m,0,sizeof(m));
	for(i = 1;i <= N;i++)
		for(j = 0;j <= mlvt;j++){
			if(j <= B[i-1].lvt && j >= B[i-1].lst){
				m[i][j] = m[i-1][j-B[i-1].lst]+B[i-1].hd;
				if(m[i][j] < m[i-1][j])m[i][j] = m[i-1][j];
			}
			else m[i][j] = m[i-1][j];
		}
	int ans = m[N][mlvt];
	for(i = 1;i <= mlvt;i++)
		if(m[N][i] > ans) ans = m[N][i];
	return ans;
		
}

int main()
{
	while(cin>>N&&N>=0){
		for(int i = 0; i < N;i++)
			cin>>B[i].hd>>B[i].lst>>B[i].lvt;
		cout<