求对拍

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

Grace25 @ 2021-08-23 16:44:08

我在AcWing上提交了这道题，但WA了

可是我在洛谷上是AC的

我也挑不出啥错来

拿了题解对拍，一个输出25，一个输出33

这把我整蒙了

求人对拍QAQ

附上代码：

#include<iostream>
using namespace std;
long long r,a[501],f[501]={0};
int main(){
    long long ans=-0x3f;
    cin >> r;
    for(int i=1;i<=r;i++){
        f[0]=0;        
        for(int j=1;j<=i;j++)
            cin >> a[j];
        for(int j=i;j>=1;j--){
            f[j]=max(f[j-1],f[j])+a[j];
            ans=max(ans,f[j]);
        }
    }
    cout << ans;
    return 0;
}

涉事数据：

10

-6

-4 -5

-3 7 5

3 7 -2 1

10 2 -6 2 -6

-8 3 8 6 7 9

-4 -10 0 -3 4 9 2

0 5 5 5 10 -6 -5 -4

-9 7 4 9 8 -5 -2 3 2

-7 -4 0 -10 -8 -4 3 -5 8 9

正确输出
25

by xieyikai2333 @ 2021-08-24 09:50:43

@Grace25 过了吗？

by xieyikai2333 @ 2021-08-24 21:40:47

@Grace25

#include<iostream>
using namespace std;
long long r,a[501],f[501];
int main(){
    long long ans=-0x3f3f3f3f;//改动1：0x3f可能不够吧 
    f[0]=-0x3f3f3f3f;//改动2： f[0]在开始的时候初始化一下就可以了 
    cin >> r;
    cin>>f[1];//改动3：第一个数直接就是f[1]的值 
    for(int i=2;/*改动4：第一行预处理过了，直接第二行开始*/i<=r;i++){
        f[i]=-0x3f3f3f3f;//改动5：金字塔每一行多一个数，f[i]是新增的，也初始化为负无穷 
        for(int j=1;j<=i;j++)
            cin >> a[j];
        for(int j=i;j>=1;j--){
            f[j]=max(f[j-1],f[j])+a[j];
//          ans=max(ans,f[j]);
        }
    }
    for(int i=1;i<=r;i++)ans=max(ans,f[i]);//改动6：因为有负数，ans可能会变小，所以最后再结算 
    cout << ans;
    return 0;
}

by Grace25 @ 2021-08-25 15:26:09

@202112xyk 好的，试试

by Grace25 @ 2021-08-25 15:32:54

@202112xyk AC了QAQ

by xieyikai2333 @ 2021-08-25 17:14:24

congratulation。。。

by woxwos001 @ 2021-11-07 19:29:15

上一页 |