青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219405
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

PKU 3093 Margaritas on the River Walk
        先對輸入的數組排序,然后類似于01對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]大,肯定這時候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[i]加進以前的選擇里面
                                         else d[i][j]++;//a[i]單獨作為一個選擇(這里需要先對a[i]排序,消除后效性)
                               }
                        }
                 }
         }

PKU 1037 A decorative fence
        先dp算出以i為起點的序列的個數,再組合數學
        td[n][i]和tu[n][i]分別表示個數為n,以i開始的上升和下降的序列個數
        易知:
        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
        雙調歐幾里德旅行商問題(明顯階段dp)
        動態規劃方程 :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
        狀態表示: d[i][j][k] (i為13為二進制表示點的狀態, j為當前節點, k為到達j的前驅節點)

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

FeedBack:
# re: 對一些DP題目的小結 2007-04-22 08:56 byron
豪大牛,問一下,這是一些題目嗎????  回復  更多評論
  
# re: 對一些DP題目的小結 2007-04-24 00:52 
@byron
是pku上的題目,我菜菜啊。。。  回復  更多評論
  
# re: 對一些DP題目的小結 2007-04-26 18:59 oyjpart
呵呵 就聊上了啊 :)  回復  更多評論
  
# re: 對一些DP題目的小結 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
  回復  更多評論
  
# re: 對一些DP題目的小結 2007-06-30 22:59 姜雨生
應該可以更加優化  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
              一区二区三区免费观看| 亚洲国产日韩精品| 欧美一区二区三区在线免费观看 | 国产在线播放一区二区三区| 久久精品72免费观看| 久久国产日本精品| 亚洲国产高清aⅴ视频| 亚洲国产综合视频在线观看| 欧美精品啪啪| 欧美自拍丝袜亚洲| 久久综合久久综合久久综合| 日韩视频在线一区二区| 国产精品99久久久久久久女警 | 久久精品亚洲一区二区| 91久久黄色| 亚洲香蕉伊综合在人在线视看| 国产毛片精品视频| 亚洲福利视频一区| 国产精品日日摸夜夜添夜夜av| 久久亚洲电影| 欧美视频日韩视频在线观看| 久久精品在线免费观看| 欧美区在线观看| 久久精品国产免费看久久精品| 久热综合在线亚洲精品| 亚洲一区二区三区精品视频| 久久精品一区二区三区不卡牛牛| 夜夜嗨av色一区二区不卡| 欧美一级理论性理论a| 99国产精品国产精品久久 | 欧美成人久久| 国产精品一区二区视频| 亚洲国语精品自产拍在线观看| 国产欧美视频一区二区三区| 亚洲国产日韩在线一区模特| 国产亚洲精品v| 日韩视频一区二区三区| 亚洲成人在线视频网站| 午夜精品网站| 亚洲一区二区三区精品视频| 欧美成ee人免费视频| 久久婷婷麻豆| 国产日韩欧美不卡在线| 一区二区国产在线观看| 亚洲精品一品区二品区三品区| 久久国产欧美日韩精品| 欧美自拍偷拍午夜视频| 欧美体内谢she精2性欧美| 亚洲国产精品毛片| 亚洲高清在线| 久久久成人网| 久久综合电影一区| 国产自产2019最新不卡| 亚洲欧美综合一区| 欧美在线视频不卡| 国产乱肥老妇国产一区二| 在线亚洲一区观看| 亚洲天堂偷拍| 国产精品成人一区二区三区吃奶| 亚洲三级电影在线观看| 亚洲免费大片| 欧美日韩国产免费| 亚洲精选在线| 亚洲主播在线播放| 国产精品高潮呻吟视频| 亚洲性色视频| 久久黄色小说| 伊人影院久久| 男女av一区三区二区色多| 欧美成人一区二区| 亚洲美女色禁图| 欧美裸体一区二区三区| 一区二区三区免费看| 亚洲一区高清| 国产综合第一页| 老司机aⅴ在线精品导航| 亚洲成人在线免费| 亚洲毛片一区二区| 蜜臀va亚洲va欧美va天堂| 中文日韩欧美| 欧美久久久久久| 欧美激情区在线播放| 亚洲人体一区| 欧美日韩亚洲精品内裤| 亚洲香蕉网站| 久久午夜国产精品| 亚洲精品婷婷| 国产精品久久午夜夜伦鲁鲁| 欧美综合国产精品久久丁香| 欧美福利视频在线| 亚洲一区二区三区精品视频| 国产伦理一区| 欧美成人午夜剧场免费观看| 夜夜嗨av一区二区三区四区| 久久久伊人欧美| 亚洲美女精品久久| 国产亚洲日本欧美韩国| 欧美jizz19性欧美| 亚洲在线不卡| 欧美成人精品在线播放| 一本色道久久综合亚洲91| 国产女主播在线一区二区| 久久深夜福利免费观看| 正在播放亚洲一区| 老司机午夜精品视频| 亚洲一区二区三区精品在线| 精品电影在线观看| 欧美视频中文一区二区三区在线观看 | 久久人人精品| 亚洲精品婷婷| 黑人极品videos精品欧美裸| 久久久久久久久伊人| 在线一区二区三区四区| 欧美激情在线有限公司| 久久精品国产清高在天天线| 中国成人在线视频| 亚洲精品1区| 亚洲专区国产精品| 亚洲国产成人一区| 国产精品99久久久久久人| 欧美日韩免费高清| 久久久久.com| 亚洲欧美日韩一区在线| 99国产麻豆精品| 亚洲第一精品福利| 久久尤物视频| 久久久天天操| 久久精品成人一区二区三区| 亚洲自拍偷拍色片视频| 亚洲美女淫视频| 亚洲精品日韩欧美| 亚洲国产精品一区制服丝袜 | 国产精品视频一区二区高潮| 欧美黄色网络| 欧美激情第二页| 欧美大片在线看免费观看| 久久天天躁狠狠躁夜夜av| 欧美在线视频日韩| 欧美成人精品高清在线播放| 欧美高清视频www夜色资源网| 亚洲国产mv| 欧美国产视频一区二区| 欧美国产国产综合| 欧美大片国产精品| 欧美激情国产日韩| 亚洲国产小视频| 亚洲精品小视频| 亚洲天堂偷拍| 亚洲欧美中日韩| 久久久久久久久久久久久女国产乱| 久久福利资源站| 男女精品视频| 欧美日韩国产小视频| 国产精品v欧美精品v日韩| 国产精品亚洲综合天堂夜夜| 国产女优一区| 揄拍成人国产精品视频| 亚洲欧洲视频| 亚洲深夜福利网站| 欧美一区三区三区高中清蜜桃| 久久久亚洲欧洲日产国码αv| 久久这里有精品视频| 亚洲国产高清一区| 久久久久久免费| 激情国产一区二区| 欧美成人综合| 久久久国产一区二区三区| 老司机精品视频网站| 欧美日韩亚洲综合在线| 国产亚洲欧美日韩日本| 亚洲国产一区二区a毛片| 亚洲手机在线| 久久婷婷久久| 日韩视频免费在线观看| 欧美在线视频在线播放完整版免费观看 | 噜噜爱69成人精品| 亚洲第一区色| 亚洲欧美日韩国产成人| 欧美制服第一页| 欧美劲爆第一页| 国产一区二区久久久| 一个色综合导航| 麻豆九一精品爱看视频在线观看免费 | 亚洲精品午夜| 亚洲欧美一区二区激情| 麻豆9191精品国产| 中国成人黄色视屏| 猫咪成人在线观看| 国产亚洲欧美日韩一区二区| 亚洲国产三级在线| 欧美一区二区三区啪啪| 亚洲欧洲在线一区| 久久精品一区二区三区不卡牛牛| 欧美日韩性视频在线| 影音先锋中文字幕一区| 亚洲欧美日韩成人高清在线一区| 欧美激情一区二区在线| 欧美在线看片a免费观看| 国产精品第一区| 一本色道久久88亚洲综合88|