一道四维dp题，虽然二维也能骗点分……

先说二维dp的思路：

二维的思路偏向贪心，即定义dp[ i ][ j ]为走到点[ i , j ]时的最佳选项，此时保证第一遍走的时候为最佳答案，第二遍走时为去掉第一遍走过的点时的最佳答案，保证两遍都是分别的最佳答案但非整体的最佳答案……，未懂的同学可以向下看，“特殊”情况：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=11;
int dp1[N][N],dp2[N][N],n,o;
struct point
{
	int x;
	int y;
	int num;
}poi[N*N];
void find(int k,int l)//判断第一遍走过哪些点 
{
	if(k==0&&l==0)
	{
		return;
	}
	else
	{
		if(dp1[k][l]-dp2[k][l]==dp1[k-1][l])
	    {  
		    dp2[k][l]=0;
		    find(k-1,l); 
	    }
	    else if(dp1[k][l]-dp2[k][l]==dp1[k][l-1])
	    {
		    dp2[k][l]=0;
		    find(k,l-1);
	    }
	}
}
int main()
{
	scanf("%d",&n);
	for(;;)
	{
		o++;
		scanf("%d%d%d",&poi[o].x,&poi[o].y,&poi[o].num);
		if(poi[o].x==poi[o].y&&poi[o].y==poi[o].num&&poi[o].num==0)
		{
			break;
		}
		else
		{
			dp1[poi[o].x][poi[o].y]=poi[o].num;
			dp2[poi[o].x][poi[o].y]=poi[o].num;
		}
	}
	for(int i=1;i<=n;i++)//第一遍的最优解 
	{
		for(int j=1;j<=n;j++)
		{
			dp1[i][j]+=max(dp1[i-1][j],dp1[i][j-1]);
		}
	}
	find(n,n);
	for(int i=1;i<=n;i++)//第二遍的最优解 
	{
		for(int j=1;j<=n;j++)
		{
			dp2[i][j]+=max(dp2[i-1][j],dp2[i][j-1]);
		}
	}
	printf("%d",dp1[n][n]+dp2[n][n]);//输出答案 
	return 0;
}

既然我们可以用dp表示每遍的最优解，那么我们可不可以用dp直接求出整体的最优解呢？当然是可以的：

我们使用dp[ i ][ j ][ k ][ l ]表示第一遍走到点[ i , j ],第二遍走到点[ k , l ]的最优解，代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=11;
int dp[N][N][N][N];
int a[N][N];
int n,x,y,z;
int main()
{
	scanf("%d",&n);
	for(;;)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(x==y&&y==z&&z==0)
		{
			break;
		}
		else
		{
			a[x][y]=z;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int l=1;l<=n;l++)
				{
					dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];
					if(i==k&&l==j)dp[i][j][k][l]-=a[i][j];//注意判断这个点走过几次并处理 
				}
			}
		}
	}
	printf("%d",dp[n][n][n][n]);
	return 0;
}

文章较长，有用就好。。。

#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
    int x,y,data;
}p[100];
int n,m,map[11][11],f[11][11][11][11];
int main()
{
    int i,j,k,l;
    scanf("%d",&n);
    while(1)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(!a&&!b&&!c)
            break;
        p[++m].x=a;
        p[m].y=b;
        p[m].data=c;
    }
    for(i=1;i<=m;i++)
        map[p[i].x][p[i].y]=p[i].data;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
            {
                l=i+j-k;
                if(l<=0)
                    break;
                f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])));
                if(i==k&&j==l)
                    f[i][j][k][l]+=map[i][j];
                else
                    f[i][j][k][l]+=map[i][j]+map[k][l];
            }
    printf("%d\n",f[n][n][n][n]);
    return 0;
}