小黃同學 @ 2018-07-17 08:10:28
大佬们,帮忙看下这道衍生题,在教练的评测平台上总是wa
题目 代码
#include<bits/stdc++.h>
using namespace std;
long long num[1010][1010],f[1010][1010];
long long n;
int dp() {
for(int i=n; i>=1; i--) {
for(int j=1; j<=i; j++) {
if(i==n) f[i][j]=num[i][j];
else
f[i][j]=num[i][j]+max(f[i+1][j],f[i+1][j+1]);
}
}
}
int main() {
cin>>n;
int x,y;
cin>>x>>y;
for(int i=1; i<=n; i++) {
for(int j=1; j<=i; j++) {
cin>>num[i][j];
}
}
num[x][y]+=327670000;
dp();
cout<<f[1][1]-327670000;
}
by 小黃同學 @ 2018-07-17 08:13:12
题目在这:数字三角形,从三角形顶部往下走,只能往左下或右下走,求走到最下面且必须经过点(x,y)所经过的数字和最大值为多少,下图为n为5的情况:
输入
- 5
- 4 2
- 7
- 3 8
- 7 6 0
- 2 7 9 4
- 4 5 2 5 3 输出:33