问题描述:
C语言问题,提供思路就行(当然有伪代码甚至完整代码就更好了)
In every summer there are students graduating from school.A lot of graduating students would like to host their parties to say good-bye to their classmates and friends.This kind of activity is called "bg" on our BBS.
Attending different parties will give you different feelings.You may assign each party a degree of happiness which is a non-negative integer that shows how you feel about attending to that party.
Now you are given a list of parties containing the length of each party and the time on which the host will be leaving school.It would be nice to schedule the parties so that you can obtain maximum of happiness.Since there could be as many as 30 parties on the list,you'll need the computer to help you.
Input Specification:
Your program must read test cases from standard input.
The input file consists of several test cases.Each case starts with an integer N ( 30),then followed by N lines each in the format
h l t
where h is the degree of happiness,l is the length of the party (in hours),and t is the hours after which the host will be leaving the school.It is guaranteed that l is no greater than t,since if the host will leave at the end of the t-th hour,the party will have to end by that time.
The input is finished by a negative N.
Output Specification:
For each test case,your program must output to standard output.First print in one line the maximum degree of happiness.In the next line print a possible schedule in the format:
i1 i2 ...ik
where i1 i2 ...ik are the index numbers of the parties (start counting from 1).
Note:once you select a party,you must join the party from the beginning to the end.The time taken to run from one party to another can be omitted.
In case that the solutions are not unique,output any one of them will do.
Sample Input:
4
5 1 1
10 2 3
6 1 2
3 1 1
-1
Sample Output:
16
3 2
In every summer there are students graduating from school.A lot of graduating students would like to host their parties to say good-bye to their classmates and friends.This kind of activity is called "bg" on our BBS.
Attending different parties will give you different feelings.You may assign each party a degree of happiness which is a non-negative integer that shows how you feel about attending to that party.
Now you are given a list of parties containing the length of each party and the time on which the host will be leaving school.It would be nice to schedule the parties so that you can obtain maximum of happiness.Since there could be as many as 30 parties on the list,you'll need the computer to help you.
Input Specification:
Your program must read test cases from standard input.
The input file consists of several test cases.Each case starts with an integer N ( 30),then followed by N lines each in the format
h l t
where h is the degree of happiness,l is the length of the party (in hours),and t is the hours after which the host will be leaving the school.It is guaranteed that l is no greater than t,since if the host will leave at the end of the t-th hour,the party will have to end by that time.
The input is finished by a negative N.
Output Specification:
For each test case,your program must output to standard output.First print in one line the maximum degree of happiness.In the next line print a possible schedule in the format:
i1 i2 ...ik
where i1 i2 ...ik are the index numbers of the parties (start counting from 1).
Note:once you select a party,you must join the party from the beginning to the end.The time taken to run from one party to another can be omitted.
In case that the solutions are not unique,output any one of them will do.
Sample Input:
4
5 1 1
10 2 3
6 1 2
3 1 1
-1
Sample Output:
16
3 2
问题解答:
我来补答展开全文阅读