自己编译器上样例过了,0分求助

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

Zzz123456789101112 @ 2024-04-09 20:00:48

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int r,ans;
    cin >> r;
    vector<vector<int>> a(r+1, vector<int>(r+1, 0));
    vector<vector<int>> dp(r+1, vector<int>(r+1, 0));//定义dp数组:到达(i,j)点的最大和
    for(int i=1;i<=r;i++ ){
        for (int j = 1; j <= i; j++)cin >> a[i][j];
    }
    for (int i = 1; i <= r; i++) {//遍历顺序,从上往下,从左往右//初始化,因为从(1,1)开始,所以可省略初始化
        for (int j = 1; j <= i; j++) {
            dp[i][j] = a[i][j]+max(dp[i - 1][j-1], dp[i - 1][j ]);
            //递归,每个位置都与上一行左右两个位置的最大和有关,并比较大小
            if (i == r) {
                ans = max(ans, dp[i][j]);
                //遍历至最后一行,在最后一行各个位置最大和取最大值
            }
        }
    }
    cout << ans;
    return 0;
}

by Light_LE @ 2024-05-10 19:38:56

看样例:

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 

你没有考虑越界这一点:

但是你没有进行边界的特殊处理(位于边界是不能减的)

位于竖边界只考虑上边,位于斜边界只考虑左上边。其他的就把两种情况都考虑进去

希望你能 AC


|