• <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>
            posts - 11, comments - 2, trackbacks - 0, articles - 0

             

            題目分類
             Bridge  過(guò)橋問(wèn)題
             Saskatchewan  離散化(geometry)
             Jolly Jumpers  水題
             Tug of War  DP
            Interpreter 模擬

            bridge:
            http://www.cnblogs.com/drizzlecrj/archive/2007/11/24/931011.html

            這篇文章有講解還有配套的題目,我不羅嗦了



            Saskatchewan:
            我是枚舉每列, 然后計(jì)算這一列的面積,再加起來(lái)就可以了
            一列中,先刪去不在當(dāng)前范圍內(nèi)的邊,再把剩下的邊排序,然后從低到高成對(duì)的考慮即可
            還有能不用 stl 的就盡量不用,很慢
            其實(shí)只要想到離散化就很簡(jiǎn)單了~~


            Tug of War:
             這個(gè)題目貌似有很多解法,我是這樣做的:
            dp[k][i][j]代表前k個(gè)人分成兩邊,其中一邊有i個(gè)人重量為j的狀態(tài)是否可以達(dá)到!
            那么dp[k][i][j]=true if and only if dp[k-1][i-1][j-H[k]]=true;其中0<=k<=100;0<=i<=50;0<=j<=450*100;在題目給3s的情況下還是可以接受的!第一維只是方便理解,實(shí)現(xiàn)同樣可以不管第一維!只要逆推就好了!
            當(dāng)處理完上面以后,假設(shè)n個(gè)人的總重量是s,最后只要從dp[n][n/2][0~s]中找到最接近s/2的那個(gè)狀態(tài)就好了~



            Interpreter:
            典型的模擬題目,只要理解了題目意思照著寫就可以了~
            這里推薦一個(gè)類似的題但是難度可能要大一些:
            http://202.120.80.191/problem.php?problemid=1840

             

            題目分類
             Freckles  圖論,最小生成樹
               
              Primary Arithmetic  簡(jiǎn)單題
             Demerit Points 模擬
            Edit Step Ladders DP加二分

            Demerit Points:
            直接按照題目模擬就好了,只是有點(diǎn)繁瑣而已!

            Edit Step Ladders:
            跟LIS的動(dòng)態(tài)規(guī)劃一樣,dp[i]表示到前前i個(gè)單詞最長(zhǎng)的,那么dp[i]=max(dp[j])+1;(0<=j<i,且word[j]可以由規(guī)則變成word[i]);轉(zhuǎn)移的時(shí)候我們可以讓word[i]通過(guò)規(guī)則生成單詞,看該單詞是否在前面出現(xiàn)過(guò)!注意我們沒(méi)必要生成所有的單詞,因?yàn)橛行颍覀冎恍枰杀葁ord[i]小的單詞!查單詞的時(shí)候可以二分查找!
            后面討論說(shuō)可以nlog(n)的,不過(guò)我暫時(shí)還沒(méi)有想到!


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            久久亚洲欧美国产精品| 久久99精品久久久久久动态图| 久久亚洲综合色一区二区三区| AA级片免费看视频久久| 一本一道久久a久久精品综合| 伊人久久大香线蕉av不卡| 国产精品久久久久久久| 要久久爱在线免费观看| 人妻丰满AV无码久久不卡| 久久久久亚洲?V成人无码| 久久青青草原精品国产| 最新久久免费视频| 精品99久久aaa一级毛片| 久久精品99久久香蕉国产色戒| 亚洲国产成人精品无码久久久久久综合 | 久久久久亚洲精品无码网址| 东方aⅴ免费观看久久av| 国产一区二区三精品久久久无广告| 久久久久亚洲精品日久生情 | 国内精品伊人久久久影院| 国产激情久久久久影院| 国产精品青草久久久久婷婷| 亚洲精品无码久久久久去q| 色99久久久久高潮综合影院| 99久久无码一区人妻| 久久精品中文字幕无码绿巨人| 久久婷婷五月综合97色直播| 国产精品女同一区二区久久| 国产99久久久久久免费看| 精品免费tv久久久久久久| 久久亚洲精品中文字幕| 国产激情久久久久久熟女老人| 久久久久波多野结衣高潮| 久久人人爽人人爽人人片AV东京热| 久久激情亚洲精品无码?V| 国产国产成人久久精品| 亚洲欧美精品伊人久久| 国产精品久久久久一区二区三区| 久久天堂电影网| 久久久久一本毛久久久| 亚洲色欲久久久久综合网|