https://www.luogu.org/problemnew/show/P1508
好了這題就是較為簡單的坐標類DP（感覺），總之是一個二維的區域，需要一步一步地向可前進方向dp，而倒退過來，就是每一個地方取之前的地方里最多的一個進行選擇，然后得出本格數量。
那么本題只能往3個方向走，如果本所在格為i,j,那么....
| i,j | ||
|---|---|---|
| i-1,j-1 | i-1,j | i-1,j+1 |
可以走到i,j的三個格子將這么表示。可得出狀態轉移方程。
f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];
其中a[i][j]為本格所獲能量值。
以上了解了之后本題就相當簡單了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define tcl(a,b,c) for(a=b;a<=c;a++)
const int maxx=201;
int n,m,a[maxx][maxx],f[maxx][maxx],i,j,x,y;
int main()
{scanf("%d%d",&n,&m);y=m/2+1;x=n;//題目所述起始位置memset(a,-10000,sizeof(a));//本題存在負能量值tcl(i,1,n){tcl(j,1,m){scanf("%d",&a[i][j]);}}tcl(i,1,n){tcl(j,1,m){f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];}}int ans;ans=max(max(f[x][y],f[x][y-1]),f[x][y+1]);//因為只能朝題中所說的三個方向走，所以自然是在這其中取最大。printf("%d",ans);return 0;
}
)
