Concert Hall Scheduling
| Time Limit: 1000MS |
|
Memory Limit: 30000K |
| Total Submissions: 574 |
|
Accepted: 229 |
Description
You are appointed director of a famous concert hall, to save it from bankruptcy. The hall is very popular, and receives many requests to use its two fine rooms, but unfortunately the previous director was not very efficient, and it has been losing money for many years. The two rooms are of the same size and arrangement. Therefore, each applicant wishing to hold a concert asks for a room without specifying which. Each room can be used for only one concert per day.
In order to make more money, you have decided to abandon the previous fixed price policy, and rather let applicants specify the price they are ready to pay. Each application shall specify a period [i, j] and an asking price w, where i and j are respectively the first and last days of the period (1 <= i <= j <= 365), and w is a positive integer in yen, indicating the amount the applicant is willing to pay to use a room for the whole period.
You have received applications for the next year, and you should now choose the applications you will accept. Each application should be either accepted for its whole period or completely rejected. Each concert should use the same room during the whole applied period.
Considering the dire economic situation of the concert hall, artistic quality is to be ignored, and you should just try to maximize the total income for the whole year by accepting the most profitable applications.
Input
The input has multiple data sets, each starting with a line consisting of a single integer n, the number of applications in the data set. Then, it is followed by n lines, each of which represents one application with a period [i, j] and an asking price w yen in the following format.
i j w
A line containing a single zero indicates the end of the input.
The maximum number of applications in a data set is one thousand, and the maximum asking price is one million yen.
Output
For each data set, print a single line containing an integer, the maximum total income in yen for the data set.
Sample Input
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640
0
Sample Output
30
25500
38595
Source
這道題目放了很久了，一直沒想出好的解法。最近的幾次比賽中都遇到了這道題，比賽后才把這題搞定。這題的方法是DP。輸入數據記錄要處理一下，開一個366大的vector數組，記錄了到第e天結束時的音樂會的開始時間s和收益w。開一個dp[366][366]的數組，其中dp[i][j]表示第一個音樂廳在第i天，第二個音樂廳在第j天收到的yen。因為預定的音樂會占用音樂廳是有一個區間的，這里做一個處理，就是在一場音樂會占用的期間都不收錢，直到一個音樂會完全結束后才收錢。另外兩個音樂廳是一樣的，即最后dp[i][j]應該是一個對稱數組，當只接受一場音樂會的情況可以強行的認為這場音樂會是放在第一個音樂廳，計算dp[i][j]中所有i>j的值，最后再令dp[j][i]=dp[i][j]即可。
1
for(i=1; i<=365; i++)
2
{
3
for(jj=0; jj<hall[i].size(); jj++)
4
{
5 for(j=0; j<i; j++)
6 {
7 dp[i][j]=Max(dp[i][j],dp[hall[i][jj].s-1][j]+hall[i][jj].w);
8
}
9 for(ii=jj+1; ii<hall[i].size(); ii++)
10 {
11 dp[i][i]=Max(dp[i][i],dp[hall[i][jj].s-1][hall[i][ii].s-1]+
12 hall[i][jj].w+hall[i][ii].w);
13 }
14 }
15 for(j=1; j<=i; j++)
16 {
17 dp[i][j]=Max(dp[i-1][j],dp[i][j]);
18 dp[i][j]=Max(dp[i][j-1],dp[i][j]);
19 dp[j][i]=dp[i][j];
20 }
21
}
posted on 2008-08-02 11:18
飛飛 閱讀(1581)
評論(0) 編輯 收藏 引用 所屬分類:
ACM/ICPC