AcWing 898. 数字三角形    原题链接    简单

作者： 作者的头像   西河二当家 ,  2020-04-28 15:29:07 ,  所有人可见 ,  阅读 942

1


1

$$ 动态规划 \begin {cases} 状态表示 f(i, j) \begin {cases} 集合：所有从起点走到(i, j)的路径\\\ 属性：路径数字和最大 \end{cases}\\\ \\\ 状态计算 \begin {cases} 分类 \begin {cases} 从左上方到达(i, j) & f(i-1, j-1) + a(i, j)\\\ 从右上方到达(i, j) & f(i-1, j) + a(i, j)\\\ \end {cases} \\\ \\\ 求解：两种可能求max \end{cases}\\\ \end {cases} $$

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, INF = 1e9;

int a[N][N], f[N][N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            scanf("%d", &a[i][j]);

    memset(f, 0x8f, sizeof f);  // 初始化为负无穷

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];

    int res = -INF;
    for (int j = 1; j <= n; j ++)
        res = max(res, f[n][j]);

    printf("%d\n", res);
    return 0;
}

6 评论

用户头像
lvky.   2021-02-07 21:10         踩      回复

为啥INF为1e9的时候， memset(f, -INF, sizeof f)，就WA呢，INF为0x3f3f3f3f的时候就过了

用户头像
西河二当家   2021-02-21 20:40         踩      回复

因为 memset(f, 0x8f, sizeof f) 是将 f 的每一个字节设置为 0x8f，而不是每一个元素。当第二个参数大于一个字节的最大值时，按照某种方式截断，所以 1e9 就 WA 了hhh

用户头像
happy8   2021-01-31 21:45         踩      回复

动态规划⎧⎩⎨⎪⎪⎪⎪⎪⎪状态表示f(i,j){集合：所有从起点走到(i,j)的路径属性：路径数字和最大状态计算⎧⎩⎨⎪⎪分类{从左上方到达(i,j)从右上方到达(i,j)f(i−1,j−1)+a(i,j)f(i−1,j)+a(i,j)求解：两种可能求max

用户头像
哈哈哈hh   2020-06-18 15:35         踩      回复

wo我这里为什么是错误的啊，

#include <iostream>
using namespace std;
#include <cstring>

const int N = 505;

const int INF = 0x3f3f3f3f;
int a[N][N];
int dp[N][N];
int main()
{
    int n = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            cin >> a[i][j];
        }
    }
    memset(dp,-INF, sizeof dp);
    dp[1][1] = a[1][1];

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

    int res = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
    {
        res = max(res,dp[n][i]);
    }
    printf("%d\n", res);
用户头像
西河二当家   2020-06-19 08:10         踩      回复

右上方是 dp[i-1][j] + a[i][j]，二维数组顺序和直角坐标系不大一样hh

用户头像
哈哈哈hh   2020-06-19 09:29    回复了 西河二当家 的评论         踩      回复

嗷嗷，懂了