@[lijinhan_bmx](/user/964822) 此题要点:
1. 不开 long long 见祖宗 O _ O
2. 从三个方向 dp ,具体见代码
\
附代码 O v O
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<functional>
#include<istream>
#include<sstream>
#include<streambuf>
#define ll long long
using namespace std;
ll r[3000],a[3000][3000],up[3000],down[3000];
//递推公式:f[i]=max(down[i],up[i]);
// up[i]=max(f[i],up[i+1])+a[i][j];
// down[i]=max(f[i],down[i-1])+a[i][j];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&a[i][j]);
r[1]=a[1][1];
for(int i=2;i<=n;i++)
r[i]=r[i-1]+a[i][1];
for(int j=2;j<m;j++)
{
memset(down,0,sizeof(down));
memset(up,0,sizeof(up));
down[1]=r[1]+a[1][j];
up[n]=r[n]+a[n][j];
for(int i=2;i<=n;i++)
down[i]=max(r[i],down[i-1])+a[i][j];
for(int i=n-1;i>=1;i--)
up[i]=max(r[i],up[i+1])+a[i][j];
for(int i=1;i<=n;i++)
r[i]=max(down[i],up[i]);
}
r[1]+=a[1][m];
for(int i=2;i<=n;i++)
r[i]=max(r[i],r[i-1])+a[i][m];
printf("%lld",r[n]);
return 0;
}
```
by wunaidedanjuan @ 2023-08-31 17:47:13
@[wunaidedanjuan](/user/951032) ?为什么没换行 Q A Q
by wunaidedanjuan @ 2023-08-31 17:47:58
我试试吧,谢谢dalao,Orz
by protractor @ 2023-08-31 17:52:03
@[wunaidedanjuan](/user/951032) 越改越乱,0分了T_T
```
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long a[1005][1005];
long long dp1[1005];
long long dp2[1005];
long long ans[1005];
int main()
{
long long n,m;
cin>>n>>m;
//dp1[0]=dp2[n+1]=-2147483647ll*2147483647;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
for(int j=1;j<=m;j++)
{
dp1[1]=ans[1]+a[1][j];
dp2[n]=ans[n]+a[n][j];
for(int i=2;i<=n;i++) dp1[i]=max(dp1[i-1],ans[i])+a[i][j];
for(int i=n-1;i>=1;i--) dp2[i]=max(dp2[i+1],ans[i])+a[i][j];
for(int i=1;i<=n;i++) ans[i]=max(dp1[i],dp2[i]);
}
ans[1]+=a[1][m];
for(int i=2;i<=n;i++) ans[i]=max(ans[i],ans[i-1])+a[i][m];
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cout<<'{'<<dp1[i][j]<<','<<dp2[i][j]<<','<<ans[i][j]<<'}'<<' ';
cout<<endl;
}*/
cout<<ans[n];
return 0;
}
```
by protractor @ 2023-08-31 18:02:32
十年OI一场空,不开long long见祖宗
by S08577 @ 2023-08-31 18:02:42
@[lijinhan_bmx](/user/964822) 你这个DP一眼假
by Light_az @ 2023-08-31 18:08:52
@[S08577](/user/950923) F4战神我开了啊
by protractor @ 2023-08-31 19:59:15
@[Light_az](/user/654958) ?
样例过了,哪错了
by protractor @ 2023-08-31 19:59:46
@[lijinhan_bmx](/user/964822)
```cpp
2 2
1 1
1 1
```
随便一组就没了
by Light_az @ 2023-08-31 20:04:25
6……
by protractor @ 2023-08-31 20:05:38