求助贪心（DP可进、暴力勿进）

Butterfly__qwq @ 2022-03-06 17:13:36

#include<bits/stdc++.h>
using namespace std;
int n[1001][1001];
int main()
{
    int p,nx=0,ny=0,ans;
    cin>>p;
    for(int i=0;i<p;i++)
        for(int j=0;j<=i;j++)cin>>n[i][j];
    ans=n[0][0];
    while(nx!=p)
    {
        if(n[nx+1][ny]>n[nx+1][ny+1])ans+=n[nx+1][ny];
        else
        {
            ans+=n[nx+1][ny+1];
            ny++;
        }
        nx++;
    }
    cout<<ans;
    return 0;
}

by Butterfly__qwq @ 2022-03-06 17:14:51

顺道求线性DP板子

虽然用F12强行改成了AC

by loverintime @ 2022-03-06 17:19:44

您都知道它是 DP 了那您还为啥要贪心呢？

by Neutralized @ 2022-03-06 17:33:10

贪心正确性证明不了为什么要用贪心（

by Butterfly__qwq @ 2022-03-06 17:37:53

@xby070301 @Neutralized

那线性DP板子是什么呢

by newbie_QwQ @ 2022-03-06 17:42:06

@蝴蝶小队队长 没有板子，要推状态转移方程才能打出DP。如果连数字三角形都不会，建议重学或找资料自学。

by newbie_QwQ @ 2022-03-06 17:44:10

@蝴蝶小队队长 还有两个问题：

1.F12只能在自己上面显示，其他人看到的还是WA。

2.DP不要用LATEX。

by Butterfly__qwq @ 2022-03-06 17:45:59

@Quhaoran123

然后呢？？？

刚学DP,太蒻了，第一道DP题

by newbie_QwQ @ 2022-03-06 17:49:09

@蝴蝶小队队长 错了。 是 max(a_{i-1,j-1},a_{i-1,j})。

by Butterfly__qwq @ 2022-03-06 17:50:27

@Quhaoran123 为甚么

by newbie_QwQ @ 2022-03-06 17:52:34

@蝴蝶小队队长 因为你是从下往上推的啊。