HDU 2571 命运
【摘要】 题目链接~~>
做题感悟:很久以前做这题一点思路也没有,但是今天一看真简单!
解题思路:方法一、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):
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
const int INF = -999999999 ;
-
const int MX= 1005 ;// 开大点
-
int n,m ;
-
int dp[25][MX] ;
-
void init()// 初始化
-
{
-
for(int i=0 ;i<=n+100 ;i++)
-
for(int j=0 ;j<=m+100 ;j++)
-
dp[i][j]=INF ;
-
}
-
int main()
-
{
-
int T ;
-
scanf("%d",&T) ;
-
while(T--)
-
{
-
scanf("%d%d",&n,&m) ;
-
init() ;
-
for(int i=1 ;i<=n ;i++)
-
for(int j=1 ;j<=m ;j++)
-
scanf("%d",&dp[i][j]) ;
-
for(int i=1 ;i<=n ;i++)
-
for(int j=1 ;j<=m ; j++)
-
{
-
int mx=INF ;
-
for(int k=2 ;k<=j ;k++)
-
if(j%k==0)
-
mx= mx < dp[i][j/k] ? dp[i][j/k] : mx ;
-
mx= mx > dp[i][j-1] ? mx : dp[i][j-1] ;
-
mx= mx > dp[i-1][j] ? mx : dp[i-1][j] ;
-
if(i!=1||j!=1) // 这一点一定要注意
-
dp[i][j]+=mx ;
-
}
-
printf("%d\n",dp[n][m]) ;
-
}
-
return 0 ;
-
}
代码(记忆化搜索):
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
const int INF = -999999999 ;
-
const int MX= 1005 ;// 开大点
-
int n,m ;
-
int g[25][MX],dp[25][MX] ;
-
int dfs(int x,int y)
-
{
-
if(dp[x][y]!=INF)
-
return dp[x][y] ;
-
int ans=INF ;
-
if(y+1<=m&&dfs(x,y+1)>ans)// 向右一步
-
ans=dfs(x,y+1) ;
-
if(x+1<=n&&dfs(x+1,y)>ans)// 向下一步
-
ans=dfs(x+1,y) ;
-
for(int k=y+y ;k<=m ;k+=y)// 走横向倍数
-
if(dfs(x,k)>ans)
-
ans=dfs(x,k) ;
-
dp[x][y]=ans+g[x][y] ;
-
return dp[x][y] ; //这里要返回dp[x][y],而不是 ans
-
}
-
void init()// 初始化
-
{
-
for(int i=0 ;i<=n ;i++)
-
for(int j=0 ;j<=m ;j++)
-
dp[i][j]=INF ;
-
}
-
int main()
-
{
-
int T ;
-
scanf("%d",&T) ;
-
while(T--)
-
{
-
scanf("%d%d",&n,&m) ;
-
init() ;
-
for(int i=1 ;i<=n ;i++)
-
for(int j=1 ;j<=m ;j++)
-
scanf("%d",&g[i][j]) ;
-
dp[n][m]=g[n][m] ; // 注意!
-
printf("%d\n",dfs(1,1)) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/20842613
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)