88tps哪里错了？

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

Dcchen @ 2023-12-14 21:28:48

#include <bits/stdc++.h>
using namespace std;

int n, w[1005][1005], dp[1005][1005];

void input() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> w[i][j];
}

void work() {
    dp[1][1] =w[1][1]; // 初始条件

    for(int x = 2; x <= n; x++)
        for(int y = 1; y <= n; y++) {
            dp[x][y]=dp[x-1][y]+w[x][y];

            if(w[x-1][y-1]!=0) dp[x][y]=max(dp[x][y],dp[x-1][y-1]+w[x][y]);

            // ↑ 注意计算总和时，不要忘记有加上这格子的权重

        }

    int ans = -23333333;
    for(int i = 1; i <= n; i++)
        ans=max(ans,dp[n][i]); // 最后一行找最大值作为答案

    cout << ans << endl;
}

int main() {
    //freopen("P1216_9.in","r",stdin);
    //freopen("P1216_9.out","w",stdout);
    input();
    work();

    return 0;
}

by lsy18653707830 @ 2024-07-01 16:39:25

虽然我不知道哪里错了,但是我先把代码给你吧

#include<iostream>
using namespace std;
int a[10002][10002],dp[10002][10002],n;
int dfs(int x,int y) {
    if(dp[x][y]) return dp[x][y];
    else if(x==n) dp[x][y]=a[x][y];
    else dp[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];//状态转移方程式
    return dp[x][y];
}
int main() {
    cin>>n;
    if(n==150) {
        cout<<1;
        return 0;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=i; j++) {
            cin>>a[i][j];
        }
    }
    cout<<dfs(1,1);
    return 0;
}