为什么2种写法得分不一样!

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

only_matthew @ 2021-10-10 16:40:44

“我从那里来”得分33

#include<cstdio>
#include<algorithm>
const int MAXN=1000+5;
int dp[MAXN][MAXN],w[MAXN][MAXN],r;
int main(){
    scanf("%d",&r);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&w[i][j]);
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
           dp[i][j]=w[i][j]+std::max(dp[i-1][j],dp[i-1][j-1]);
        }
    }
    printf("%d",dp[r][r]);
    return 0;
}

“我到那里去”AC

#include<cstdio>
#include<algorithm>
const int MAXN=1000+5;
int dp[MAXN][MAXN],w[MAXN][MAXN],r;
int main(){
    scanf("%d",&r);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&w[i][j]);
    for(int i=r;i>0;i--){
        for(int j=1;j<=i;j++){
           dp[i][j]=w[i][j]+std::max(dp[i+1][j],dp[i+1][j+1]);
        }
    }
    printf("%d",dp[1][1]);
    return 0;
}

by lailai0916 @ 2021-10-10 16:41:16


by danaqi @ 2021-10-10 16:52:34

最后一列取最值


by huwanpeng @ 2021-10-10 16:52:52

@only_matthew

最高点到底部任意处结束的路径

你第一个代码

dp[i][j]=w[i][j]+std::max(dp[i-1][j],dp[i-1][j-1]);

是从下往上累加


|