#3 号点没过,请求大佬指导

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

Light_LE @ 2024-05-10 19:31:01

是不是没有加特殊判断吧?

89pts 代码

#include<iostream>
#include<limits.h>
using namespace std;
const int maxn=1003;
int n,dp[maxn][maxn],a[maxn][maxn],ans=INT_MIN;
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);

    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cin>>a[i][j];
        }
    }

    dp[0][0]=a[0][0];
    for(int i=1;i<n;i++){
        for(int j=0;j<=i;j++){
            if(j==0){
                dp[i][j]=dp[i-1][j]+a[i][j];
            }
            else if(i==j){
                dp[i][j]=dp[i-1][j-1]+a[i][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
            }

            if(i==n-1){
                ans=max(ans,dp[i][j]);
            }
        }
    }
    cout<<ans;
    return 0;
}

by Light_LE @ 2024-05-10 20:13:48

已过


|