33分求助

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

xyz123hhh @ 2023-04-06 14:27:30

#include<iostream>
#include<algorithm>
using namespace std;
long dp[10000][10000];
long n;
long i;
int main()
{
    cin>>n;
    for(long i=1;i<=n;i++)
    {
        for(long j=1;j<=i;j++)
        {
            cin>>dp[i][j];
        }
    }
    long o=0;
    long u=0;
    for(long i=2;i<=n;i++)
    {
        for(long j=1;j<=i;j++)
        {
            o=dp[i-1][j-1];
            u=dp[i-1][j];
            if(o>u)
            {
                dp[i][j]+=dp[i-1][j-1];
            }
            dp[i][j]+=dp[i-1][j];

        }
    }
    long t =0;
    for(long i=1;i<=n;i++)                                    
    {
        t=max(t,dp[i][n]);

    }
    cout<<t<<endl;
    return 0;

}

by Smithespics @ 2023-04-07 17:16:17

@xyz123hhh 你的错误有点多,居然还能有33pts（不可思议）

  1. 你的循环体有问题：对于三角形每一层的最左边和最右边两个边需要单独讨论，他们肯定是只能加上上一层最左边和最右边的值。其次，可以直接用max函数解决的事情，就不需要再麻烦的引入u、o两个变量了。

    for(long i=2;i<=n;i++)
{
    dp[i][1]+=dp[i-1][1];
    for(long j=2;j<i;j++)
    {
        dp[i][j]+=max(dp[i-1][j],dp[i-1][j-1]);
    }
    dp[i][i]+=dp[i-1][i-1];
}
  2. 你的输出有问题，你需要输出的是最后一层的最大的dp值你为什么会输出dp[i][n]?
t=max(t,dp[i][n]);
//正确做法应该是t=max(t,dp[n][i]);

希望对你有帮助，其次推荐你可以去再学习一下滚动数组的知识。

|