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

            Sephiroth's boring days!!!

            Love just for you.

            動態規劃-走迷宮問題

            [題目描述]

            有一個n*n的迷宮,每個方格里都有著相應的數字。你從左上角出發,每次可以向上下左右四個方向最多移動k格,并且要求你每次到達的方格里的數字必須大于上一次所在方格的數字。現在要求你走過的方格的所有數之和最大,問這個最大和是多少。

            [輸入]

            輸入數據第一行為兩個正整數N、K(1<=N<=100,0<=K<=N)

            接下來的n行,每行有n個不超過integer范圍的整數,表示地圖中的數。

            [輸出]

            輸出數據只有一行,為最大的和。

            [輸入輸出示例]

            輸入(maze.in) 輸出(maze.out)

            3 1 25

            3 6 2

            4 7 9

            2 3 1

            [評分標準]

            對于每個測試數據,如果你能夠得出正確的答案,那么你將得到滿分,否則得0分。

            [分析]

            很明顯的動態規劃,應該是從《滑雪》那道題改編而來的。

              1: #include <stdio.h>
            
              2: #define maxn 110
            
              3: 
            
              4: int a[maxn][maxn];
            
              5: int f[maxn][maxn];
            
              6: int n,ans,k;
            
              7: int xx[4]={0,0,1,-1};
            
              8: int yy[4]={1,-1,0,0};
            
              9: 
            
             10: int find(int x,int y)
            
             11: {
            
             12:     if (f[x][y]) return f[x][y];
            
             13:     int temx,temy;
            
             14:     for (int i=0;i<4;++i)
            
             15:         for (int j=1;j<=k;++j)
            
             16:         {
            
             17:             temx=x+xx[i]*j;
            
             18:             temy=y+yy[i]*j;
            
             19:             if ((temx>0)&&(temx<=n)&&(temy>0)&&(temy<=n))
            
             20:                 if ((a[temx][temy]>a[x][y])&&(find(temx,temy)>f[x][y]))
            
             21:                     f[x][y]=find(temx,temy);
            
             22:         }
            
             23:     f[x][y]+=a[x][y];
            
             24:     return f[x][y];
            
             25: }
            
             26: 
            
             27: int main()
            
             28: {
            
             29:     freopen("maze.in","r",stdin);
            
             30:     freopen("maze.out","w",stdout);
            
             31:     
            
             32:     scanf("%d%d",&n,&k);
            
             33:     for (int i=1;i<=n;++i)
            
             34:         for (int j=1;j<=n;++j)
            
             35:             scanf("%d",&a[i][j]);
            
             36:     printf("%d\n",find(1,1));
            
             37:     return 0;
            
             38: }
            
             39: 

            posted on 2010-08-31 19:52 Sephiroth Lee 閱讀(1449) 評論(0)  編輯 收藏 引用 所屬分類: 信息奧賽

            free counters
            久久精品国产亚洲av日韩| 久久99精品久久久久久| 久久久高清免费视频| 久久久久免费精品国产| 久久久国产精品亚洲一区| 欧美激情精品久久久久| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 国产69精品久久久久9999APGF| 久久精品国产乱子伦| 青青草原综合久久大伊人精品| 久久精品国产乱子伦| 久久se这里只有精品| 99久久99久久精品免费看蜜桃| 国产亚洲精久久久久久无码AV| 亚洲综合熟女久久久30p| 久久成人国产精品一区二区| 国产精品九九九久久九九| 久久久噜噜噜久久中文字幕色伊伊 | 久久久久亚洲AV成人片| 人人狠狠综合久久亚洲高清| 国产一区二区三区久久| 亚洲精品乱码久久久久久按摩 | 久久久国产精品| 91久久成人免费| 久久精品国内一区二区三区| 久久人人爽人人爽人人AV东京热| 欧美久久天天综合香蕉伊| 国产成人精品久久亚洲高清不卡 | 久久无码人妻一区二区三区午夜| 久久亚洲国产精品成人AV秋霞| 欧美一级久久久久久久大| 青青草原综合久久大伊人导航| 99久久久久| 久久精品成人免费国产片小草| 久久久久一区二区三区| 亚洲国产二区三区久久| 国产综合成人久久大片91| 精品乱码久久久久久夜夜嗨| 久久996热精品xxxx| 亚洲精品无码久久久久AV麻豆| 久久久久久久久66精品片|