求助贪心(DP可进、暴力勿进)

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

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:54:07


by Butterfly__qwq @ 2022-03-06 18:00:52

@Quhaoran123 谢谢巨佬


by Butterfly__qwq @ 2022-03-06 18:04:58


by Butterfly__qwq @ 2022-03-06 18:07:24

@Quhaoran123 还有一个问题:DP和贪心都是找局部最优解,为甚么DP✔,贪心❌


by Engulf @ 2022-04-10 23:41:59

@蝴蝶小队队长

     1
   2    3
 114514  10

此时贪心算法是错误的。


by Butterfly__qwq @ 2022-04-11 21:15:47

@TMJYH09 谢谢


上一页 |