Eric12 @ 2021-11-12 21:59:37
//如果把题目中看成直角三角形的话,可以向下或向右走。
//思想:等腰三角形--三角形--正方形
#include <iostream>
#include <cstdio>
using namespace std;
int r,a[1001][1001],x,y,f[1001][1001],nowmax=-9999999,nowx=1,nowy=1;
char c;
int main()
{
cin>>r;
c=getchar();//第一个数输入完后,会有换行\n输入。
while(nowx<=r)
{
c=getchar();
if(c!=' '&&c!='\n')
{
a[nowx][nowy]=c-'0';
nowy++;
}
else if(c=='\n')
{
nowx++;
nowy=1;
}
}
f[1][1]=a[1][1];
for(int i=2;i<=r;i++)
f[i][1]=f[i-1][1]+a[i][1];
for(int i=2;i<=r;i++)//行
for(int j=2;j<=r;j++)//列
{
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
nowmax=max(nowmax,f[i][j]);
}
cout<<nowmax<<endl;
return 0;
}
by Eric12 @ 2021-11-12 22:02:41
还有,f是DP数组,表示(1,1)点到(下标1,下标2)的最大路径总数。