大佬 求解啊

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

小黃同學 @ 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

|