社区讨论

「站外题目求助」数字三角形 2

学术版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lyu9ussq
此快照首次捕获于
2024/07/20 23:16
2 年前
此快照最后确认于
2024/07/21 09:23
2 年前
查看原帖

题目

数字三角形 要求走到最后的和mod  100最大
题目图片1
每个数只能通过连线从上往下走

输入

第1行n,表示n行  < =25 第2到n+1行为每个的权值

输出

mod  100最大值

样例

样例输入1

2 1 99 98

样例输出1

99

评测结果

13个测试点,共对了7个点

代码

C
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;

const int N = 2e3 + 10;

int mp[N][N], d[N][N];

signed main()
{
	int n;
	cin >> n ;
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = 1; j <= i; ++ j)
		{
			cin >> mp[i][j] ;
		}
	} 
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = 1; j <= i; ++ j)
		{
			d[i][j] = max(d[i - 1][j - 1] + mp[i][j] % 100, d[i - 1][j] + mp[i][j] % 100);
		}
	}
	int ans = 0; 
	for(int i = 1; i <= n; ++ i)
	{
		// cout << d[n][i] << " " ;
		ans = max(ans, d[n][i] % 100);
	}
	cout << ans ;
	return 0;
}

大体思路

递推,递推式为 d[i][j]=max(d[i1][j1]+mp[i][j]d[i][j] = max(d[i - 1][j - 1] + mp[i][j] % 100, d[i - 1][j] + mp[i][j] % 100),最后再遍历二维数组(矩阵)的最后一行取最大值(中间已经对100取模)

某位大佬的回复

感觉有点没听懂
大佬回复
希望大佬们能给出详细的解释

回复

1 条回复,欢迎继续交流。

正在加载回复...