题解 | #[NOIP2000]方格取数#

//*多维动态规划朴素版*//
//*可以根据数学一维平面直角坐标系斜截式用对角线及平行线来优化可以降为3阶dp[对角线][x1][x2]或用y1,y2同理
*//#include<iostream>
#include<algorithm>
using namespace std;
const int N=11;
int map[N][N]={0};
int dp[N][N][N][N]={0,0,0,0};
int dx1[4]={1,0,1,0};
int dy1[4]={0,1,0,1};
int dx2[4]={1,0,0,1};
int dy2[4]={0,1,1,0};
bool b;
int main()
{
    int n,x,y,w,x1,y1,x2,y2;
    cin>>n;
    while(cin>>x>>y>>w)
    {
      if(x==0&&y==0&&w==0)
      break;
      map[x][y]=w;  
    }
    dp[1][1][1][1]=map[1][1];
    for(x1=1;x1<=n;x1++)
     for(y1=1;y1<=n;y1++)
      for(x2=1;x2<=n;x2++)
	   for(y2=1;y2<=n;y2++)
        {
          b=(x1==x2)&&(y1==y2);
          int temp=b?map[x1][y1]:map[x1][y1]+map[x2][y2];
          dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2-1][y2]+temp,dp[x1][y1][x2][y2]);
          dp[x1][y1][x2][y2]=max(dp[x1][y1-1][x2][y2-1]+temp,dp[x1][y1][x2][y2]);
          dp[x1][y1][x2][y2]=max(dp[x1-1][y1][x2][y2-1]+temp,dp[x1][y1][x2][y2]);
          dp[x1][y1][x2][y2]=max(dp[x1][y1-1][x2-1][y2]+temp,dp[x1][y1][x2][y2]);
        }  
    cout<<dp[n][n][n][n];
    return 0;
}