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 谢谢