• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            alpc60 ACM/ICPC程序設(shè)計(jì)
            成長(zhǎng)的路……源
            posts - 20,comments - 42,trackbacks - 0
                
            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。輸入數(shù)據(jù)記錄要處理一下,開一個(gè)366大的vector數(shù)組,記錄了到第e天結(jié)束時(shí)的音樂會(huì)的開始時(shí)間s和收益w。開一個(gè)dp[366][366]的數(shù)組,其中dp[i][j]表示第一個(gè)音樂廳在第i天,第二個(gè)音樂廳在第j天收到的yen。因?yàn)轭A(yù)定的音樂會(huì)占用音樂廳是有一個(gè)區(qū)間的,這里做一個(gè)處理,就是在一場(chǎng)音樂會(huì)占用的期間都不收錢,直到一個(gè)音樂會(huì)完全結(jié)束后才收錢。另外兩個(gè)音樂廳是一樣的,即最后dp[i][j]應(yīng)該是一個(gè)對(duì)稱數(shù)組,當(dāng)只接受一場(chǎng)音樂會(huì)的情況可以強(qiáng)行的認(rèn)為這場(chǎng)音樂會(huì)是放在第一個(gè)音樂廳,計(jì)算dp[i][j]中所有i>j的值,最后再令dp[j][i]=dp[i][j]即可。

             1for(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 飛飛 閱讀(1592) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC
            亚洲综合久久夜AV | 午夜精品久久久久久| 婷婷久久综合九色综合绿巨人| 亚洲va中文字幕无码久久不卡| 狠狠色综合久久久久尤物| 久久线看观看精品香蕉国产| 久久人爽人人爽人人片AV| 亚洲精品无码久久一线| 久久99久国产麻精品66| 午夜天堂av天堂久久久| 久久亚洲欧美国产精品| 久久精品一本到99热免费| 久久AV高清无码| 久久中文字幕一区二区| 国产精品熟女福利久久AV| 久久人妻少妇嫩草AV无码蜜桃| 中文字幕亚洲综合久久菠萝蜜| 亚洲国产精品无码久久青草| 中文字幕久久亚洲一区| 国产成人精品久久亚洲| 精品久久久久久无码免费| 思思久久精品在热线热| 97热久久免费频精品99| 91精品国产高清91久久久久久| 日本五月天婷久久网站| 久久久久无码精品国产不卡| 人妻少妇久久中文字幕| 亚洲狠狠婷婷综合久久久久| 国产精品久久久久无码av| 国产免费久久久久久无码| 一本久久精品一区二区| AAA级久久久精品无码片| 91久久婷婷国产综合精品青草| 久久精品成人免费观看97| 久久久久久久女国产乱让韩| 亚洲国产精品久久久久网站 | 久久精品人人做人人爽电影蜜月| 久久无码国产| 麻豆精品久久久久久久99蜜桃| 一本久久精品一区二区| 久久精品国产日本波多野结衣|