• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2007年6月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217820
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            PKU 3093 Margaritas on the River Walk
                    先對(duì)輸入的數(shù)組排序,然后類似于01對(duì)a[i]做決策,核心代碼加了注釋:
                     for (i=1; i<=n; i++) {
                             for (j=1; j<=maxsum; j++) {
                                    if (j >= sum[i]) d[i][j] = 1; //j比sum[i]大,肯定這時(shí)候d[i][j]=1;
                                    else {
                                            d[i][j] = d[i-1][j];//不考慮a[i]
                                            if (j-a[i]>=0) {//考慮a[i]
                                                     if (d[i-1][j-a[i]] > 0) d[i][j] += d[i-1][j-a[i]];//把a(bǔ)[i]加進(jìn)以前的選擇里面
                                                     else d[i][j]++;//a[i]單獨(dú)作為一個(gè)選擇(這里需要先對(duì)a[i]排序,消除后效性)
                                           }
                                    }
                             }
                     }

            PKU 1037 A decorative fence
                    先dp算出以i為起點(diǎn)的序列的個(gè)數(shù),再組合數(shù)學(xué)
                    td[n][i]和tu[n][i]分別表示個(gè)數(shù)為n,以i開始的上升和下降的序列個(gè)數(shù)
                    易知:
                    td[n][1] = 0;
                    td[n][i] = sigma(tu[n-1][j], j從1..i-1)  = td[n][i-1] + tu[n-1][i-1] ;
                    tu[n][i]  = td[n][n+i-1];

            PKU 2677 Tour
                    雙調(diào)歐幾里德旅行商問題(明顯階段dp)
                    動(dòng)態(tài)規(guī)劃方程 :d[i+1][i] = mint(d[i+1][i], d[i][j]+g[j][i+1]); 
                                                  d[i+1][j] = mint(d[i+1][j], d[i][j]+g[i][i+1]);
                                                   0<=j<i   

            PKU 2288 Islands and Bridges
                    集合DP
                    狀態(tài)表示: d[i][j][k] (i為13為二進(jìn)制表示點(diǎn)的狀態(tài), j為當(dāng)前節(jié)點(diǎn), k為到達(dá)j的前驅(qū)節(jié)點(diǎn))

            posted on 2007-04-20 18:10 閱讀(2127) 評(píng)論(5)  編輯 收藏 引用 所屬分類: 算法&ACM

            FeedBack:
            # re: 對(duì)一些DP題目的小結(jié) 2007-04-22 08:56 byron
            豪大牛,問一下,這是一些題目嗎????  回復(fù)  更多評(píng)論
              
            # re: 對(duì)一些DP題目的小結(jié) 2007-04-24 00:52 
            @byron
            是pku上的題目,我菜菜啊。。。  回復(fù)  更多評(píng)論
              
            # re: 對(duì)一些DP題目的小結(jié) 2007-04-26 18:59 oyjpart
            呵呵 就聊上了啊 :)  回復(fù)  更多評(píng)論
              
            # re: 對(duì)一些DP題目的小結(jié) 2007-06-30 22:55 姜雨生
            Margaritas on the River Walk
            Time Limit:1000MS Memory Limit:65536K
            Total Submit:309 Accepted:132

            Description


            One of the more popular activities in San Antonio is to enjoy margaritas in the park along the river know as the River Walk. Margaritas may be purchased at many establishments along the River Walk from fancy hotels to Joe’s Taco and Margarita stand. (The problem is not to find out how Joe got a liquor license. That involves Texas politics and thus is much too difficult for an ACM contest problem.) The prices of the margaritas vary depending on the amount and quality of the ingredients and the ambience of the establishment. You have allocated a certain amount of money to sampling different margaritas.

            Given the price of a single margarita (including applicable taxes and gratuities) at each of the various establishments and the amount allocated to sampling the margaritas, find out how many different maximal combinations, choosing at most one margarita from each establishment, you can purchase. A valid combination must have a total price no more than the allocated amount and the unused amount (allocated amount – total price) must be less than the price of any establishment that was not selected. (Otherwise you could add that establishment to the combination.)

            For example, suppose you have $25 to spend and the prices (whole dollar amounts) are:

            Vendor A B C D H J
            Price 8 9 8 7 16 5

            Then possible combinations (with their prices) are:

            ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) and HJ(21).

            Thus the total number of combinations is 15.


            Input


            The input begins with a line containing an integer value specifying the number of datasets that follow, N (1 ≤ N ≤ 1000). Each dataset starts with a line containing two integer values V and D representing the number of vendors (1 ≤ V ≤ 30) and the dollar amount to spend (1 ≤ D ≤ 1000) respectively. The two values will be separated by one or more spaces. The remainder of each dataset consists of one or more lines, each containing one or more integer values representing the cost of a margarita for each vendor. There will be a total of V cost values specified. The cost of a margarita is always at least one (1). Input values will be chosen so the result will fit in a 32 bit unsigned integer.


            Output


            For each problem instance, the output will be a single line containing the dataset number, followed by a single space and then the number of combinations for that problem instance.


            Sample Input


            2
            6 25
            8 9 8 7 16 5
            30 250
            1 2 3 4 5 6 7 8 9 10 11
            12 13 14 15 16 17 18 19 20
            21 22 23 24 25 26 27 28 29 30

            Sample Output


            1 15
            2 16509438

            Hint


            Note: Some solution methods for this problem may be exponential in the number of vendors. For these methods, the time limit may be exceeded on problem instances with a large number of vendors such as the second example below.


            Source
            Greater New York 2006
              回復(fù)  更多評(píng)論
              
            # re: 對(duì)一些DP題目的小結(jié) 2007-06-30 22:59 姜雨生
            應(yīng)該可以更加優(yōu)化  回復(fù)  更多評(píng)論
              
            综合久久国产九一剧情麻豆 | 久久久久久久亚洲Av无码| 婷婷国产天堂久久综合五月| 丁香色欲久久久久久综合网| 久久精品国产秦先生| 久久成人小视频| 久久久久免费精品国产| 亚洲?V乱码久久精品蜜桃 | 人妻少妇精品久久| 1000部精品久久久久久久久| 偷窥少妇久久久久久久久| 国产精品美女久久久久av爽| 亚洲人成伊人成综合网久久久| 国产精品免费久久久久影院| 久久精品国产亚洲av水果派| 中文成人久久久久影院免费观看| 久久福利青草精品资源站免费 | 久久精品国产99国产精品| 国产精品一久久香蕉国产线看观看 | 天堂久久天堂AV色综合| 香蕉久久久久久狠狠色| 精品熟女少妇aⅴ免费久久| 青青青青久久精品国产| 亚洲AV日韩AV永久无码久久| 亚洲精品成人久久久| 国产精品久久久99| 国产精品成人99久久久久| 狠狠色婷婷综合天天久久丁香 | 欧美喷潮久久久XXXXx| 色婷婷久久久SWAG精品| 理论片午午伦夜理片久久| 人妻中文久久久久| 色老头网站久久网| 国产色综合久久无码有码| 久久亚洲精品无码VA大香大香| 伊人久久无码精品中文字幕| 久久久这里只有精品加勒比 | …久久精品99久久香蕉国产| 国产精品久久毛片完整版| 久久精品成人免费网站| 国产午夜精品久久久久九九电影|