y总讲的炒鸡好!
但是
我快被那个鬼畜边界弄疯了
y总讲的是从三角形上方往下顺推
我来一个逆推
其实也不逆啦就是
往上爬
为什么我要往上爬呢
因为我不想处理那么多边界情况,一不小心就死翘翘了
所以我还是往上爬吧
(虽然要克服重力做功我这么胖也不容易)
我这个甚至不用考虑有没有负数!
原因自己想啦
代码来一波
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 2e9;
int f[1001][1001];
int n,a[1001][1001];
int main() {
scanf("%d",&n);
for(register int i=1; i<=n; i++)
for(register int j=1; j<=i; j++)
scanf("%d",&a[i][j]);
for(register int i=n; i>=1; i--)
for(register int j=i; j>=1; j--)
f[i][j] += max(f[i+1][j] , f[i+1][j+1]) + a[i][j];
printf("%d\n",f[1][1]);
return 0;
}
最后!
我们来对比一下顺着三角形往下滑(顺推)的代码
(不用克服重力可是你摩擦生热不烫吗)
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int a[1001][1001];
int f[1001][1001];
int n,ans=-INF;
int main() {//这个玩意是顺推的
scanf("%d",&n);
for(register int i=1; i<=n; i++)
for(register int j=1; j<=i; j++)
scanf("%d",&a[i][j]);
for(register int i=0; i<=n; i++) //注意要从0到n(一共n+1个数)
for(register int j=0; j<=i+1; j++)//而且这里要每行多初始化一个
f[i][j] = -INF;
f[1][1] = a[1][1];
for(register int x=2; x<=n; x++)//魔鬼边界,这儿从2开始
for(register int y=1; y<=x; y++)//但是这儿从1开始
f[x][y] = max(f[x-1][y-1] , f[x-1][y]) + a[x][y];
for(register int i=1; i<=n; i++) ans = max(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
//别忘了-INF(见上)
//来自算法基础课
最后的最后
这个故事告诉我们
看上去艰难的路途不一定费力
看上去安逸的大道也不一定闲适
不管前途如何
要敢于尝试
(说不定顺便就减肥了呢对吧)
register是什么意思、作用和应用范围,大佬能解释下吗
你太逗了
顺推初始化的时候,i 可以直接从1~n-1 吧;因为我们下头f 【1,1】已经确定了,从x=2开始的;
而第 n 排也不用初始化吧,因为没有用到;这样貌似也能过
退役将近两个月啦)我的程序没有初始化哦,下面那个是y总的code