HDU 2571 命运

举报
Linux猿 发表于 2021/08/05 00:11:52 2021/08/05
【摘要】 题目链接~~> 做题感悟:很久以前做这题一点思路也没有,但是今天一看真简单! 解题思路:方法一、dp: dp[ i ][ j ] = max ( dp[ i ][ j - 1 ]  , dp[ i - 1 ][ j ] , dp[ i ][ k ]) ( k 为 j 的真因子) . 方法二、记忆化搜索(都要注意初始化) 代码(DP): #in...

题目链接~~>

做题感悟:很久以前做这题一点思路也没有,但是今天一看真简单!

解题思路:方法一、dp: dp[ i ][ j ] = max ( dp[ i ][ j - 1 ]  , dp[ i - 1 ][ j ] , dp[ i ][ k ]) ( k 为 j 的真因子) . 方法二、记忆化搜索(都要注意初始化)

代码(DP):


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<string>
  5. #include<string.h>
  6. #include<stdlib.h>
  7. #include<math.h>
  8. #include<vector>
  9. #include<queue>
  10. #include<algorithm>
  11. using namespace std ;
  12. const int INF = -999999999 ;
  13. const int MX= 1005 ;// 开大点
  14. int n,m ;
  15. int dp[25][MX] ;
  16. void init()// 初始化
  17. {
  18. for(int i=0 ;i<=n+100 ;i++)
  19. for(int j=0 ;j<=m+100 ;j++)
  20. dp[i][j]=INF ;
  21. }
  22. int main()
  23. {
  24. int T ;
  25. scanf("%d",&T) ;
  26. while(T--)
  27. {
  28. scanf("%d%d",&n,&m) ;
  29. init() ;
  30. for(int i=1 ;i<=n ;i++)
  31. for(int j=1 ;j<=m ;j++)
  32. scanf("%d",&dp[i][j]) ;
  33. for(int i=1 ;i<=n ;i++)
  34. for(int j=1 ;j<=m ; j++)
  35. {
  36. int mx=INF ;
  37. for(int k=2 ;k<=j ;k++)
  38. if(j%k==0)
  39. mx= mx < dp[i][j/k] ? dp[i][j/k] : mx ;
  40. mx= mx > dp[i][j-1] ? mx : dp[i][j-1] ;
  41. mx= mx > dp[i-1][j] ? mx : dp[i-1][j] ;
  42. if(i!=1||j!=1) // 这一点一定要注意
  43. dp[i][j]+=mx ;
  44. }
  45. printf("%d\n",dp[n][m]) ;
  46. }
  47. return 0 ;
  48. }

代码(记忆化搜索):


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<string>
  5. #include<string.h>
  6. #include<stdlib.h>
  7. #include<math.h>
  8. #include<vector>
  9. #include<queue>
  10. #include<algorithm>
  11. using namespace std ;
  12. const int INF = -999999999 ;
  13. const int MX= 1005 ;// 开大点
  14. int n,m ;
  15. int g[25][MX],dp[25][MX] ;
  16. int dfs(int x,int y)
  17. {
  18. if(dp[x][y]!=INF)
  19. return dp[x][y] ;
  20. int ans=INF ;
  21. if(y+1<=m&&dfs(x,y+1)>ans)// 向右一步
  22. ans=dfs(x,y+1) ;
  23. if(x+1<=n&&dfs(x+1,y)>ans)// 向下一步
  24. ans=dfs(x+1,y) ;
  25. for(int k=y+y ;k<=m ;k+=y)// 走横向倍数
  26. if(dfs(x,k)>ans)
  27. ans=dfs(x,k) ;
  28. dp[x][y]=ans+g[x][y] ;
  29. return dp[x][y] ; //这里要返回dp[x][y],而不是 ans
  30. }
  31. void init()// 初始化
  32. {
  33. for(int i=0 ;i<=n ;i++)
  34. for(int j=0 ;j<=m ;j++)
  35. dp[i][j]=INF ;
  36. }
  37. int main()
  38. {
  39. int T ;
  40. scanf("%d",&T) ;
  41. while(T--)
  42. {
  43. scanf("%d%d",&n,&m) ;
  44. init() ;
  45. for(int i=1 ;i<=n ;i++)
  46. for(int j=1 ;j<=m ;j++)
  47. scanf("%d",&g[i][j]) ;
  48. dp[n][m]=g[n][m] ; // 注意!
  49. printf("%d\n",dfs(1,1)) ;
  50. }
  51. return 0 ;
  52. }



 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/20842613

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。