HDU2571(记忆化搜索)

绝地灬酷狼 2022-05-29 00:15 164阅读 0赞

<table style="font-family:'Times New Roman';"> 
 <tbody> 
  <tr> 
   <td align="center"><h1 style="color:rgb(26,92,200);text-align:center;"><span style="font-family:'Times New Roman';font-size:14px;">命运</span></h1><span style="font-family:'Times New Roman';font-size:14px;"><strong><span style="color:#008000;">Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others)<br>Total Submission(s): 21252&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 7400<br></span></strong><br><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Problem Description</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <span style="font-size:14px;">穿过幽谷意味着离大魔王lemon已经无限接近了！<br>可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！<br>可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！<br>命运大迷宫可以看成是一个两维的方格阵列，如下图所示：<br><img src="http://acm.hdu.edu.cn/data/images/C164-1005-1.jpg" style="border:none;" alt="">&nbsp;<br>yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒，所以每个格子都对应一个值，走到那里便自动得到了对应的值。<br>现在规定yifenfei只能向右或者向下走，向下一次只能走一格。但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k&gt;1。&nbsp;<br>为了能够最大把握的消灭魔王lemon，yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。<br><img src="http://acm.hdu.edu.cn/data/images/C164-1005-2.jpg" style="border:none;" alt=""><br></span> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Input</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <span style="font-size:14px;">输入数据首先是一个整数C，表示测试数据的组数。<br>每组测试数据的第一行是两个整数n,m，分别表示行数和列数(1&lt;=n&lt;=20,10&lt;=m&lt;=1000)；<br>接着是n行数据，每行包含m个整数，表示n行m列的格子对应的幸运值K ( |k|&lt;100 )。<br></span> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Output</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <span style="font-size:14px;">请对应每组测试数据输出一个整数，表示yifenfei可以得到的最大幸运值。</span> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Sample Input</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <pre style="white-space:pre-wrap;margin-bottom:0px;font-size:14px;"></pre> 
     <div style="font-family:'Courier New', Courier, monospace;"> 
      <span style="font-family:'Times New Roman';font-size:14px;">1 3 8 9 10 10 10 10 -10 10 10 10 -11 -1 0 2 11 10 -20 -11 -11 10 11 2 10 -10 -10</span> 
     </div> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Sample Output</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <pre style="white-space:pre-wrap;margin-bottom:0px;font-size:14px;"></pre> 
     <div style="font-family:'Courier New', Courier, monospace;"> 
      <span style="font-family:'Times New Roman';font-size:14px;">52</span> 
     </div> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Author</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <span style="font-size:14px;">yifenfei</span> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Source</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=ACM%B3%CC%D0%F2%C9%E8%BC%C6%C6%DA%C4%A9%BF%BC%CA%D4081230&amp;source=1&amp;searchmode=source" style="color:rgb(26,92,200);" rel="nofollow"><span style="font-size:14px;">ACM程序设计期末考试081230</span></a> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div><span style="font-family:'Times New Roman';font-size:14px;"><br></span> 
    <div style="height:38px;background:transparent url(&quot;panel-title.png&quot;) no-repeat left bottom;padding:0px 14px;color:rgb(124,169,237);font-size:18px;font-family:Arial;font-weight:bold;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">Recommend</span> 
    </div> 
    <div style="height:auto;background:url(&quot;panel-content.png&quot;) repeat-y;margin:0px;padding:0px 20px;font-family:'Times New Roman';"> 
     <span style="font-size:14px;">yifenfei</span> 
    </div> 
    <div style="height:auto;margin:0px;background:url(&quot;panel-bottom.png&quot;) no-repeat left top;"> 
     <span style="font-family:'Times New Roman';font-size:14px;">&nbsp;</span> 
    </div></td> 
  </tr> 
  <tr> 
   <td><span style="font-family:'Times New Roman';font-size:14px;"><br></span></td> 
  </tr> 
 </tbody> 
</table>

纪念第一次自己用记忆化搜索写出一道题。

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int mod=100000000;
    const int INF=-0x3f3f3f3f;
    int mp[25][1010];
    int dp[25][1010];
     int T, n, m;
    
    int dfs(int x, int y){
        if(x==0 || y==0)
            return INF;
        if(dp[x][y]!=INF)
            return dp[x][y];
    
        int mxx=INF;
        mxx=max(mxx, dfs(x-1, y));
        mxx=max(mxx, dfs(x, y-1));
        for(int i=1; i<y; i++)
            if(y%i==0)
                mxx=max(mxx, dfs(x, i));
        return dp[x][y]=mxx+mp[x][y];

}
    
    int main(){
    
        scanf("%d", &T);
        while(T--){
    
            for(int i=0; i<=20; i++)
                for(int j=0; j<=1000; j++)
                        dp[i][j]=INF;//初始为负无穷
    
            scanf("%d%d", &n, &m);
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    scanf("%d", &mp[i][j]);
            dp[1][1]=mp[1][1];
    
            printf("%d\n", dfs(n, m));
    
        }
        return 0;
    }