• <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>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            //MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋

            題目地址: 
                     http://acm.hdu.edu.cn/showproblem.php?pid=1176
            題目描述:
                     都說天上不會(huì)掉餡餅,但有一天gameboy正走在回家的小徑上,忽然天上掉下大把大把的餡餅。說來gameboy的人品實(shí)在是太好了,這餡餅別處都不掉,就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了,所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人,所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲,雖然在游戲中是個(gè)身手敏捷的高手,但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍,每秒種只有在移動(dòng)不超過一米的范圍內(nèi)接住墜落的餡餅?,F(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo).
            為了使問題簡(jiǎn)化,假設(shè)在接下來的一段時(shí)間里,餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置,因此在第一秒,他只能接到4,5,6這三個(gè)位置中期中一個(gè)位置上的餡餅。問gameboy最多可能接到多少個(gè)餡餅?(假設(shè)他的背包可以容納無窮多個(gè)餡餅)

            很簡(jiǎn)單的一道 DP 題目, 初看起來似乎很難, 但是自習(xí)分析,會(huì)發(fā)現(xiàn) , 這其實(shí)就是

                                                      數(shù)塔 

                                             的一道變形題!!!!  
            狀態(tài)轉(zhuǎn)移方程 :
             

            pea[i-1][j] =  pea[i-1][j]  + max (   pea[i][j-1],  pea[i][j] ,  pea[i][j+1] ) ;

            下面照例是貼代碼 :
            //MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋

            #include 
            <iostream>
            using std::max;
            const int MAX_NUM = 100002;
            int pea[MAX_NUM][11];
            void setZero ( int t )
            {
                 
            for ( int i = 0; i <= t; ++i )
                 {
                      
            for ( int j = 0; j != 11++ j )
                      {
                          pea[i][j] 
            = 0;
                      }
                 }
            }
            int main ()
            {
                
            int N,temp = MAX_NUM;
                
            while ( scanf ("%d",&N), N != 0 )
                {
                      setZero ( temp );
                      
            int pos,sec;
                      
            int maxSec = 0;
                      
            for ( int i = 0; i != N; ++i )
                      {
                           scanf ( 
            "%d%d",&pos,&sec ) ;
                           pea[sec][pos] 
            ++ ;
                           
            if ( maxSec < sec )
                           {
                                maxSec 
            = sec;
                           }
                      } 
                      temp 
            = maxSec;
                     
            for ( int i = maxSec; i != 0  ; -- i )
                     {
                          
            for ( int j = 0; j != 11++ j )
                          {
                               
            if ( j == 0 )
                               {
                                    pea[i
            -1][j] += max ( pea[i][0] , pea[i][1] );
                               }
                               
            else if ( j == 10 ) 
                               {
                                    pea[i
            -1][j] += max ( pea[i][9], pea[i][10] );  
                               }
                               
            else
                               {
                                    pea[i
            -1][j] += max ( max ( pea[i][j-1], pea[i][j] ), pea[i][j+1] );
                               }   
                         }
                     }    
                     printf ( 
            "%d\n",pea[0][5] );  
                }
                
            return 0
            }

            国产精品九九久久免费视频| 九九99精品久久久久久| 国产免费久久精品丫丫| 久久人人爽人人澡人人高潮AV | 久久久噜噜噜久久中文字幕色伊伊| 欧美亚洲另类久久综合| 精品无码久久久久久久动漫| 热久久国产欧美一区二区精品 | 亚洲国产一成久久精品国产成人综合 | 四虎亚洲国产成人久久精品| 久久久久综合中文字幕 | 国内精品久久久久久久97牛牛| 国产成人久久精品一区二区三区 | 久久精品国产精品亜洲毛片| 久久久精品国产| 国产激情久久久久影院小草 | 久久人做人爽一区二区三区| 一本久久久久久久| 久久99精品久久久久子伦| 无码人妻久久一区二区三区蜜桃| 狠狠色丁香婷婷久久综合不卡| 久久人人爽人人爽人人片AV不| 九九热久久免费视频| 久久精品国内一区二区三区| 久久精品国产亚洲AV电影| 国内精品久久久久影院老司| 久久综合九色欧美综合狠狠 | 久久精品国产91久久综合麻豆自制| 久久久亚洲精品蜜桃臀| 亚洲国产精品久久| 国产精品久久久久一区二区三区| 久久99国产综合精品| 国产亚洲精品美女久久久| 亚洲AV无码1区2区久久| 久久亚洲国产成人精品性色| 亚洲伊人久久精品影院 | 亚洲AV无码久久精品狠狠爱浪潮| 青青热久久国产久精品| 伊人久久大香线蕉无码麻豆 | 国产精品久久久久…| 久久免费精品视频|