• <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>
            voip
            風(fēng)的方向
            厚德致遠(yuǎn),博學(xué)敦行!
            posts - 52,comments - 21,trackbacks - 0

            免費(fèi)餡餅

            Time Limit:1000MS  Memory Limit:65536K
            Total Submit:615 Accepted:149

            Description

            都說(shuō)天上不會(huì)掉餡餅,但有一天gameboy正走在回家的小徑上,忽然天上掉下大把大把的餡餅。說(shuō)來(lái)gameboy的人品實(shí)在是太好了,這餡餅別處都不掉,就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當(dāng)然就不能吃了,所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人,所以他只能在小徑上接。由于gameboy平時(shí)老呆在房間里玩游戲,雖然在游戲中是個(gè)身手敏捷的高手,但在現(xiàn)實(shí)中運(yùn)動(dòng)神經(jīng)特別遲鈍,每秒種只有在移動(dòng)不超過(guò)一米的范圍內(nèi)接住墜落的餡餅。現(xiàn)在給這條小徑如圖標(biāo)上坐標(biāo):

             


            為了使問(wèn)題簡(jiǎn)化,假設(shè)在接下來(lái)的一段時(shí)間里,餡餅都掉落在0-10這11個(gè)位置。開始時(shí)gameboy站在5這個(gè)位置,因此在第一秒,他只能接到4,5,6這三個(gè)位置中期中一個(gè)位置上的餡餅。問(wèn)gameboy最多可能接到多少個(gè)餡餅?(假設(shè)他的背包可以容納無(wú)窮多個(gè)餡餅)

             

            Input

            輸入數(shù)據(jù)有多組。每組數(shù)據(jù)的第一行為以正整數(shù)n(0 < n < 100000),表示有n個(gè)餡餅掉在這條小徑上。在結(jié)下來(lái)的n行中,每行有兩個(gè)整數(shù)x,T(0 <= T < 100000),表示在第T秒有一個(gè)餡餅掉在x點(diǎn)上。同一秒鐘在同一點(diǎn)上可能掉下多個(gè)餡餅。n=0時(shí)輸入結(jié)束。

            Output

            每一組輸入數(shù)據(jù)對(duì)應(yīng)一行輸出。輸出一個(gè)整數(shù)m,表示gameboy最多可能接到m個(gè)餡餅。
            提示:本題的輸入數(shù)據(jù)量比較大,建議用scanf讀入,用cin可能會(huì)超時(shí)。

            Sample Input

            6
            5 1
            4 1
            6 1
            7 2
            7 2
            8 3
            0
            

             

            Sample Output

            4
            

             

            Source

            hdu1176

                                    這個(gè)題目也屬于簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題目,如果直觀的從深度搜索的方法去做可能會(huì)超時(shí),很多時(shí)候我們采用數(shù)組填表的方式求解,以空間換取時(shí)間!!
                                    如果這個(gè)題目還有個(gè)小變化,就是撿餅人一開始站在5號(hào)位置,所以如果往我們直接從上往下求,只能求得最后每個(gè)點(diǎn)上的最優(yōu)值,所以我們應(yīng)該從后往前求,求得第一秒的時(shí)候每個(gè)點(diǎn)上的最優(yōu)值,也就是題目要求的解!!
            代碼如下:
            #include<cstdio>
            #include
            <cstdlib>
            #include
            <cstring>
            int time[100001][11];
            int max(int x,int y,int z)
            {
                
            if(x>y)
                    
            if(x>z)
                        
            return x;
                    
            else
                        
            return z;
                
            else
                    
            if(y>z)
                        
            return y;
                    
            else
                        
            return z;
            }

            int main()
            {
                
            int i,j,k,n,x,y;
                
            while(scanf("%d",&n)!=EOF&&n!=0)
                
            {
                    memset(time,
            0,sizeof(time));
                    k
            =0;
                    
            for(i=0;i<n;i++)
                    
            {
                        scanf(
            "%d %d",&y,&x);
                        time[x][y]
            ++;
                        
            if(x>k)
                            k
            =x;
                    }

                    
            /*        for(i=2;i<k'i++)
                    {
                        for(j=0;j<11;j++)
                        {
                            if(j>0&&j<10)
                                time[i][j]+=max(time[i-1][j-1],time[i-1][j],time[i-1][j+1]);
                            else if(j==0)
                                time[i][j]+=max(0,time[i-1][j],time[i-1][j+1]);
                            else
                                time[i][j]+=max(0,time[i-1][j-1],time[i-1][j]);
                        }
                    }
            */

                    
            for(i=k-1;i>=0;i--)
                    
            {
                        
            for(j=0;j<11;j++)
                        
            {
                            
            if(j>0&&j<10)
                                time[i][j]
            +=max(time[i+1][j-1],time[i+1][j],time[i+1][j+1]);
                            
            else if(j==0)
                                time[i][j]
            +=max(0,time[i+1][j],time[i+1][j+1]);
                            
            else
                                time[i][j]
            +=max(0,time[i+1][j-1],time[i+1][j]);
                        }

                    }

                    printf(
            "%d\n",time[0][5]);
                }

                
            return 0;
            }

            posted on 2010-09-14 15:22 jince 閱讀(1245) 評(píng)論(2)  編輯 收藏 引用 所屬分類: Questions

            FeedBack:
            # re: 免費(fèi)餡餅
            2011-04-25 20:58 | fghgf
            #include <iostream>
            using namespace std;
            int a[100002][12];

            int main()
            {
            int i,j,k,x,y,tt,maxx,n;
            while(scanf("%d",&n),n)
            {
            memset(a,0,sizeof(a));
            maxx=-1;
            for(i=0;i<n;i++)
            {
            scanf("%d%d",&x,&y);
            if((y<5&&x>=5-y&&x<=5+y)||(y>=5))
            a[y][x]++;
            if(maxx<y) maxx=y;
            }
            for(i=2;i<=maxx;i++)
            {
            a[i][0]+=a[i-1][0]>a[i-1][1] ? a[i-1][0]:a[i-1][1];
            a[i][10]+=a[i-1][9]>a[i-1][10] ? a[i-1][9]:a[i-1][10];
            for(j=1;j<10;j++)
            {
            k=a[i-1][j]>a[i-1][j-1] ? a[i-1][j]:a[i-1][j-1];
            a[i][j]+=k>a[i-1][j+1] ? k:a[i-1][j+1];
            }
            }
            tt=-1;
            for(i=0;i<=10;i++)
            if(tt<a[maxx][i]) tt=a[maxx][i];
            printf("%d\n",tt);
            }
            return 0;
            }







              回復(fù)  更多評(píng)論
              
            # re: 免費(fèi)餡餅[未登錄](méi)
            2011-04-25 21:03 | jince
            @fghgf
            有什么出入么?  回復(fù)  更多評(píng)論
              
            哈哈哈哈哈哈
            亚洲?V乱码久久精品蜜桃| 久久无码人妻一区二区三区午夜 | 精品久久久久久国产牛牛app| 久久久噜噜噜久久熟女AA片| 久久国产精品成人免费 | 午夜欧美精品久久久久久久| 精品国产VA久久久久久久冰| 久久精品夜色噜噜亚洲A∨ | 中文字幕成人精品久久不卡| 无码人妻久久一区二区三区蜜桃| 麻豆一区二区99久久久久| 国产精品成人精品久久久| 久久夜色精品国产亚洲| 亚洲综合精品香蕉久久网97| 2021国产精品久久精品| 国产精品亚洲美女久久久| 无码人妻久久一区二区三区免费| 久久播电影网| 久久九九亚洲精品| 久久男人Av资源网站无码软件| 久久久久99精品成人片| 欧美久久精品一级c片片| 精品综合久久久久久97| 免费精品久久久久久中文字幕 | 精品无码久久久久久久久久| 久久婷婷五月综合97色一本一本| 久久免费视频6| 草草久久久无码国产专区| 国产成人久久精品区一区二区| 中文字幕精品无码久久久久久3D日动漫| 中文字幕一区二区三区久久网站 | 国产精品成人久久久| 久久久久婷婷| 久久嫩草影院免费看夜色| 97精品伊人久久久大香线蕉| 久久久久久a亚洲欧洲aⅴ| 久久综合九色综合97_久久久| 国产亚洲综合久久系列| 狠狠干狠狠久久| 99热都是精品久久久久久| 国产一久久香蕉国产线看观看|