• <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 - 195,  comments - 30,  trackbacks - 0

            2nd JOJ Cup Online VContest Problem

            We all know that bunny is fond of carrots. One cloudy day, he was told that there would be a violenting flood coming soon to destroy the forests. He was scared and after not thinking too much he told himself that he had to escape. He suddenly recalled that there was a temple on the top of the hill and he might shelter there until the flood's past. But unfortunately there was no food for him on the top of the hill, so he had to take his carrots away along with himself. Then he moved to the foot of the hill and stopped. There was only one way for him to get the top of the hill, that is, a long staircase. Given the number of the steps of the staircase, he asked himself:"how many different ways of strides are there for him to get the top of the hill?". Of course, because of his height, he could only stride a limited range of steps. He was smart so much so that he got the answer quickly. Do you know how he did it?

            Input Specification

            The input consists of several test cases, each of which occupies a line containing M(1<=M<=40) and N(1<=N<=10), where M indicates the number of the steps of the staircase and N indicates the maximal number of steps the bunny can stride once.

            Output Specification

            Each test case should correspond to a line in the output. Your program should print an integer which is the answer.

            Sample Input

            4 2
            5 4

            Sample Output

            5
            15


            題意是一只兔子要到距離為M(單位為1)的地方,它每步最多走N,問有多少種方法。輸入M  N 輸出r[m][n];


            解析:設為r[i][j],表示距離總共i且每次最多走j的方法數(可以沒有走出那大小為j的那步,只是允許走那步而已)。

            根據最后那一步可能走的長度,r[i-2][j]表示最后那步距離為2.r[i-j][j]表示最后那步距離為j.
            建立遞推關系r[i][j]=r[i-1][j]+r[i-2][j]+r[i-3][j]+r[i-j][j];
            //本人覺得這里特別難想,想到了也覺得無法建立遞推關系呀,j不是一直不變嗎?
            神奇的地方在于可以令r[0][j]=r[1][j]=1;當然還有r[i][1]=1
            -----------預處理----
            for(j=0;j<n;j++)

                   {

                          r[0][j]=1;

                          r[1][j]=1;

                   }

                   for(i=0;i<n;i++)

                          r[i][1]=1;


            ---dp----------
             for(i=2;i<m;i++)
                for(j=2;j<n;j++)
                {
                 if(i<j)
                    r[i][j]=r[i][i]; //這點非常重要
                 else 
                   for(k=1;k<=j;k++)
                    {
               r[i][j]+=r[i-k][j];
                    }
                }
            ------------
            r[1][1]=1
            r[2][1]=1
            r[2][2]=r[2][1]+r[2][2]=2;
            r[3][1]=1;
            r[3][2]=r[2][2]+r[1][2]=3;
            r[3][3]=r[0][3]+r[1][3]+r[2][3]=4;

            posted on 2009-07-20 17:19 luis 閱讀(555) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
            <2011年11月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久天天躁狠狠躁夜夜96流白浆 | 久久精品极品盛宴观看| 久久精品国产WWW456C0M| 久久亚洲国产成人影院网站| 无码8090精品久久一区| 亚洲香蕉网久久综合影视| 久久久久久久亚洲Av无码| 亚洲午夜久久影院| 久久中文字幕人妻丝袜| 久久99精品久久久久久动态图| 热re99久久精品国产99热| 亚洲欧洲久久久精品| 97久久综合精品久久久综合| 国产农村妇女毛片精品久久| 色婷婷久久久SWAG精品| 国内精品久久久久久野外| 伊人久久大香线蕉成人| 一本大道加勒比久久综合| 老司机午夜网站国内精品久久久久久久久 | 中文字幕无码av激情不卡久久| 欧洲成人午夜精品无码区久久| 国产成人综合久久精品尤物| 五月丁香综合激情六月久久 | 99久久国产综合精品网成人影院| 久久国产AVJUST麻豆| 91精品国产高清久久久久久91| 久久久亚洲欧洲日产国码二区 | 久久亚洲欧洲国产综合| 欧美伊香蕉久久综合类网站| 亚洲中文字幕久久精品无码喷水| 久久伊人中文无码| 深夜久久AAAAA级毛片免费看| 国产日韩久久免费影院| 91久久精品国产91性色也| 99999久久久久久亚洲| 久久精品国产久精国产思思| 热re99久久精品国99热| 午夜久久久久久禁播电影| 精品久久亚洲中文无码| 伊人久久国产免费观看视频| 国内精品伊人久久久影院|