社区讨论
「站外题目求助」数字三角形 2
学术版参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lyu9ussq
- 此快照首次捕获于
- 2024/07/20 23:16 2 年前
- 此快照最后确认于
- 2024/07/21 09:23 2 年前
题目
数字三角形 要求走到最后的和mod 100最大

每个数只能通过连线从上往下走
输入
第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;
}
大体思路
递推,递推式为 ,最后再遍历二维数组(矩阵)的最后一行取最大值(中间已经对100取模)
某位大佬的回复
感觉有点没听懂

希望大佬们能给出详细的解释
回复
共 1 条回复,欢迎继续交流。
正在加载回复...