蓝桥杯算法训练VIP-方格取数 （C语言代码）--------------------C语言——菜鸟级

思路：双线程 dp 

这一题的话，题目其实是可以稍微转化一下的额，一个人走两遍跟两个人同时同速度一人走一格是等价的，

就相当于i+j==i1+j1,这表示一人走一格；

然后就比较简单了。dp[i][j][i1][j1]表示两个人在(i, j)和(i1, j1)所能得到的最大值；

注意事项:

参考代码:

#include<stdio.h>
#include<string.h>
#define Max(a,b) a>b?a:b
int main()
{ int n,s,x,y,i,j,i1,j1;int a[11][11];int dp[12][12][12][12];
scanf("%d\n",&n);
memset(dp,0,sizeof(dp));
while(1)
{scanf("%d%d%d",&x,&y,&s);
if(x==0&&y==0&&s==0)break;//输入终止 
else a[x][y]=s;
}
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   for(i1=1;i1<=n;i1++)
    for(j1=1;j1<=n;j1++)
    {
    if(i+j!=i1+j1)continue;//不是一人一步 
int tem=Max(dp[i-1][j][i1][j1-1],dp[i-1][j][i1-1][j1]); 
 tem=Max(tem,dp[i][j-1][i1][j1-1]);
 tem=Max(tem,dp[i][j-1][i1-1][j1]);
if(i==i1&&j==j1)dp[i][j][i1][j1]=a[i][j]+tem;
else dp[i][j][i1][j1]=a[i][j]+a[i1][j1]+tem ; 
   
    }
printf("%d\n",dp[n][n][n][n]);
return 0;
}