首页 > 代码库 > hdu 2571 命运 （递推）
hdu 2571 命运 （递推）
http://acm.hdu.edu.cn/showproblem.php?pid=2571
思路：
dp[i+1][j]=max(dp[i+1][j],dp[i][j]+mat[i+1][j]); dp[i][j+1]=max(dp[i][j+1],dp[i][j]+mat[i][j+1]); k=2; while(k*j<=m) { dp[i][k*j]=max(dp[i][k*j],dp[i][j]+mat[i][k*j]); k++; }
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>using namespace std;#define INF 1000000000int mat[30][2000];int dp[30][2000];int main(){ int t,n,m; int i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { dp[i][j]=-INF; scanf("%d",&mat[i][j]); } } dp[1][1]=mat[1][1]; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { dp[i+1][j]=max(dp[i+1][j],dp[i][j]+mat[i+1][j]); dp[i][j+1]=max(dp[i][j+1],dp[i][j]+mat[i][j+1]); k=2; while(k*j<=m) { dp[i][k*j]=max(dp[i][k*j],dp[i][j]+mat[i][k*j]); k++; } } } /*for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",dp[i][j]); } cout<<endl; }*/ printf("%d\n",dp[n][m]); } return 0;}
hdu 2571 命运 （递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。