刚学dp,11分其余全RE,找大佬指点一下,谢谢

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

caibishiwo @ 2022-04-13 00:13:07

#include<iostream>
using namespace std;
int temp[1001][1001];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n ; i++)
    {
        for(int j=0;j<=i;j++)
        {
            scanf("%d",&temp[i][j]); 
        }   
    }
    int ans = temp[0][0];
    for(int i = 1;i < n;i++){
        for(int j = 0;j <= i; i++){
            if(j == 0) temp[i][j] = temp[i-1][j] + temp[i][j];
            else 
            {
                temp[i][j] = max(temp[i-1][j-1] , temp[i][j-1]) + temp[i][j];
                ans = max(ans,temp[i][j]);
            }
        }
    }
    cout<<ans;
    return 0;
}

by _maojun_ @ 2022-04-13 07:20:47

它不能从同层转移过来,要从上一层的转移。

temp[i][j] = max(temp[i-1][j-1] , temp[i-1][j]) + temp[i][j];

其他应该没问题的。


|