问题标题: 酷町堂:4969   英灵殿

0
0
已解决
许致远
许致远
中级守护
中级守护

4969   英灵殿     经验值:800

题目描述 Description

芬里尔喵终于击败了邪恶的奥丁。他手持着昆古尼尔,在英灵殿中寻找宝物。英灵殿可以看成是一个m*n个格子组成的巨大房间。英灵殿的宝器太多了,芬里尔喵给每个格子的宝器分配了一个价值,w[i][j]。芬里尔喵最初处在巨大房间的左上角,她朝着右下角的出口寻觅。由于英灵殿的魔法力量的封印,她每次只能朝右方或者下方前进。请你帮她计算一下,最后总共最多能获得的宝器的价值是多少。

输入描述 Input Description

第一行,两个整数,m n
接下来m行,第i行有n个空格隔开的整数,第j个值表示w[i][j]

输出描述 Output Description

最多能获得的宝器的总价值

样例输入 Sample Input

5 5 1 5 4 10 15 2 32 6 8 17 15 26 3 18 34 3 6 9 12 16 1 21 10 4 16

样例输出 Sample Output

151

数据范围及提示 Data Size & Hint

m, n<=10

许致远在2021-03-28 18:01:16追加了内容

许致远在2021-03-28 18:09:54追加了内容

急急急

许致远在2021-03-28 18:14:46追加了内容

哪里错了

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
#include<iomanip>
#include<sstream>
using namespace std;
int ans,m,n,a[20][20];
long long f(int i,int j){
	return max(f(i-1,j),f(i,j-1))+a[i][j];
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	cout<<f(n,m);
	return 0;
}

 


0
已采纳
邹昊轩
邹昊轩
资深光能
资深光能

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

if(i==1&&j==1)

f[1][1]=a[1][1];

else if(i==1){

f[i][j]=f[i][j-1]+a[i][j];

}

else if(j==1)

{ f[i][j]=f[i-1][j]+a[i][j];

}

else{

f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];

}

}

}

核心,输出f[m][n]

自求多福吧。

我要回答