题目网址：http://acm.fzu.edu.cn/problem.php?pid=2234

#include"stdio.h"
_int64 dp[105][105][200];
_int64 max(_int64 a,_int64 b)
{return a>=b?a:b;
}
int main()
{_int64 const min=1e18;int i,j,k,n;int Ilie,Jlie;int value,ai[110][110];while(scanf("%d",&n)==1){for (i=0;i<=n;i++){for (j=0;j<=n;j++){for (k=0;k<=2*n-2;k++){dp[i][j][k]=-min;}}}for (i=1;i<=n;i++){for (j=1;j<=n;j++){scanf("%d",&ai[i][j]);}}dp[1][1][0]=ai[1][1];for (k=1;k<=2*n-2;k++){for (i=1;i<=n;i++){for (j=1;j<=n;j++){Ilie=k-i+2;Jlie=k-j+2;value=0;if (i==1&&j==1&&Ilie==1&&Jlie==1){continue;}if (Ilie>=1&&Ilie<=n&&Jlie>=1&&Jlie<=n){if (i==j&&Ilie==Jlie){value=ai[i][Ilie];}elsevalue=ai[i][Ilie]+ai[j][Jlie];dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+value);dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+value);dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+value);dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+value);}}}}printf("%I64d\n",dp[n][n][2*n-2]);}return 0;
}

动态规划好题，我们可以理解为有两个人同时从起点走到终点，动态转移方程中dp[i][j][k],i,j,j分别表示第一个人的行，第二个人的行和步数