51nod 1083 矩阵取数问题【动态规划】
2024-08-30 20:47:44
一个N*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,从左上走到右下,只能向下向右走,求能够获得的最大价值。
例如:3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为:11。
收起
输入
第1行:N,N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行:每行N个数,中间用空格隔开,对应格子中奖励的价值。(1 <= N[i] <= 10000)
输出
输出能够获得的最大价值。
输入样例
3
1 3 3
2 1 3
2 2 1
输出样例
11
思路:动态规划题最重要的就是要推导出递推式,首先设立dp数组,dp[i][j]表示坐标(i,j)处的最大值,由于只能向右或者向下,所以dp[i][j]的值就为dp[i][j],dp[i-1][j]+m[i][j]和dp[i][j-1]+m[i][j] 中最大的。
另外要注意边界的处理,看代码大家应该可以理解,
#include<cstdio>
#include <iostream>
using namespace std;
//const int mod=1e9+7;
const int maxn=505;
int dp[maxn][maxn],m[maxn][maxn];
int maxthree(int a,int b,int c)
{
a=a>b?a:b;
a=a>c?a:c;
return a;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&m[i][j]);
dp[0][0]=m[0][0];
for(int i=1;i<n;++i)
{
dp[i][0]=dp[i-1][0]+m[i][0];
dp[0][i]=dp[0][i-1]+m[0][i];
}
for(int i=1;i<n;++i)
{
for(int j=1;j<n;++j)
{
dp[i][j]=maxthree(dp[i][j],dp[i-1][j]+m[i][j],dp[i][j-1]+m[i][j]);
}
}
printf("%d\n",dp[n-1][n-1]);
return 0;
}
最新文章
- DPM算法源程序voc-release5在Windows中的配置修改过程
- C++ 基础知识复习(三)
- linux地址空间划分
- leetcode:Multiply Strings
- the jar file rt.jar has no source attachment
- idea java项目部署至Tomcat服务器
- ssh爆破(python脚本)
- maven项目-修复Plugin execution not covered by lifecycle configuration: org.codehaus.mojo:build-helper-maven-plugin:1.8:add-resource (execution: add-resource, phase: generate-resources)	pom.xml报错
- python第三天基础之字符编码
- JS基础篇-- body.scrollTop与documentElement.scrollTop
- web开发中的两把锁之数据库锁:(高并发--乐观锁、悲观锁)
- 2017-2018 Exp5 MSF基础应用 20155214
- Android轻量级ORM框架ActiveAndroid入门教程(转)
- CentOS7上Mongodb安装、卸载
- pandas:apply和transform方法的性能比较
- 回答了这四个问题,你就可以打造最佳App首页
- 2.Python输入pip命令出现Unknown or unsupported command &#39;install&#39;问题解决
- luogu P1440 求m区间内的最小值
- 「日常训练」The Intriguing Obsession(CodeForces Round #439 Div.2 C)
- Android 游标