Palace

NC230373. Palace

描述

在一个 $n\times m$ 大小的宫殿里面，每个坐标点 $(i,j)(i\in[1,n],j\in[1,m])$ 处都有一件价值为 $w_{ij}$ 的物品。

现在小明站在起点 $(1,1)$ 位置，他想走到目标点 $(n,m)$ 处，规定小明每次只能向下或者向右移动（不限移动次数）。

问：小明从起点移动到目标点时总共可以拿走最多多少价值的物品，并输出该价值的大小。

输入描述

第 $1$ 行输入两个正整数 $n$ 和 $m$ ，表示宫殿的大小 $(1 \leq n,m\leq 100)$ 。

第 $2-n+1$ 行每行输入 $m$ 个正整数 $w_{ij}(1\leq i\leq n,1\leq j\leq m)$ ，输入数据之间用空格隔开， $w_{ij}$ 表示坐标 $(i,j)$ 处的物品价值 $(1\leq w_{ij}\leq 10^4)$ 。

输出描述

输出答案。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C 解法, 执行用时: 4ms, 内存消耗: 384K, 提交时间: 2022-03-31 19:53:04

#include<stdio.h>
int a[101][101];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			int t=a[i-1][j];
			if(a[i][j-1]>t)
			t=a[i][j-1];
			a[i][j]=a[i][j]+t;
		}
	printf("%d",a[n][m]);
	return 0;
}

C++ 解法, 执行用时: 7ms, 内存消耗: 568K, 提交时间: 2021-11-13 14:48:17

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long f[200][200],n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
       cin>>f[i][j];f[i][j]+=max(f[i-1][j],f[i][j-1]);}
    cout<<f[n][m]<<'\n';return 0;
}