• <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)  編輯 收藏 引用 所屬分類: 動態規劃
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久亚洲中文字幕精品一区| 久久九九青青国产精品| 久久99热精品| 久久本道久久综合伊人| 一级做a爰片久久毛片看看| 久久精品国产99国产精品导航| 99久久国产精品免费一区二区| 久久国产精品成人片免费| 99久久精品无码一区二区毛片| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区| 亚洲欧洲精品成人久久曰影片| 久久亚洲AV成人无码电影| 最新久久免费视频| 久久精品嫩草影院| 欧美精品国产综合久久| 亚洲狠狠综合久久| 老色鬼久久亚洲AV综合| 欧洲国产伦久久久久久久| 国内精品久久久久| 久久亚洲熟女cc98cm| 久久婷婷色综合一区二区| 久久国产乱子伦精品免费强| 亚洲精品无码专区久久久| 久久综合九色综合欧美就去吻 | 久久综合久久综合九色| 久久久www免费人成精品| 国产福利电影一区二区三区久久久久成人精品综合 | 色播久久人人爽人人爽人人片AV| 久久精品国产99国产精偷| 亚洲va久久久噜噜噜久久狠狠| 久久午夜福利电影| 久久精品国产一区二区 | 亚洲另类欧美综合久久图片区| 久久国产一区二区| 亚洲国产精品无码久久SM| 久久天天躁狠狠躁夜夜avapp| 久久免费视频6| 久久精品亚洲欧美日韩久久| 久久精品国产亚洲7777| 欧美成a人片免费看久久| 热RE99久久精品国产66热|