caozy623's Blog

怎么说呢……这不就是一道双取方格数的题目，记得不错提高组考过差不多的题目，不过这题的范围更强一点。这样就必须优化到3维。

其实确定了前三个数，最后一个数是可以算出来的。。。所以就解决了。注意特判下一些特殊情况……这里如果来回路过同一个方格是

不能取两次的。别的没什么了。。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
	char x=getchar();
	while(!(x>='a'&&x<='z'))x=getchar();
	while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int f[305][305][305];
int n;
int a[305][305];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    f[i][j][k]=-inf;
    f[1][1][1]=a[1][1];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int p=1;p<=n;p++)
	{
		int q=i+j-p;
		if (q<=0) continue;
		if (i!=1&&p!=1)
		{
			int k=f[i-1][j][p-1]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (i!=1&&q!=1)
		{
			int k=f[i-1][j][p]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (j!=1&&p!=1)
		{
			int k=f[i][j-1][p-1]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
		if (j!=1&&q!=1)
		{
			int k=f[i][j-1][p]+a[i][j]+a[p][q];
			if (i==p && j==q) k-=a[i][j];
			f[i][j][p]=max(f[i][j][p],k);
		}
	}
    printf("%d\n",f[n][n][n]);
    return 0;
}