一次走2*n-2步，每步已知横坐标可以求得纵坐标，所以子状态转移为f[走的步数][第一次横坐标][第二次横坐标][第三次横坐标]

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int f[20 + 2][20 + 2][20 + 2][20 + 2][20 + 2][20 + 2];
int t[20 + 2][20 + 2];

inline int max( int a , int b )
{
if( a > b )
return a;
return b;
}

int n;
int i , j;

int dp( int a1 , int b1 , int a2 , int b2 , int a3 , int b3 )
{
if( a1 == n && b1 == n && a2 == n && b2 == n && a3 == n && b3 == n )
return t[n][n];
if( a1 > n || b1 > n || a2 > n || b2 > n || a3 > n || b3 > n )
return -100000000;
if( f[a1][b1][a2][b2][a3][b3] != -1 )
return f[a1][b1][a2][b2][a3][b3];
if( a1 == a2 && a2 == a3 && b1 == b2 && b2 == b3 )
return f[a1][b1][a2][b2][a3][b3] = t[a1][b1] + max( max( max( dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) ,max( max( dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) );
if( a1 == a2 && b1 == b2 )
return f[a1][b1][a2][b2][a3][b3] = t[a1][b1] + t[a3][b3] + max( max( max( dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) ,max( max( dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) );
if( a1 == a3 && b1 == b3 )
return f[a1][b1][a2][b2][a3][b3] = t[a3][b3] + t[a2][b2] + max( max( max( dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) ,max( max( dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) );
if( a2 == a3 && b2 == b3 )
return f[a1][b1][a2][b2][a3][b3] = t[a1][b1] + t[a2][b2] + max( max( max( dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) ,max( max( dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) );
return f[a1][b1][a2][b2][a3][b3] = t[a1][b1] + t[a2][b2] + t[a3][b3] + max( max( max( dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 + 1 , b1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) ,max( max( dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 + 1 , b2 , a3 , b3 + 1 ) ) , max( dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 + 1 , b3 ) , dp( a1 , b1 + 1 , a2 , b2 + 1 , a3 , b3 + 1 ) ) ) );
}

int main()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
scanf( "%d" , &t[i][j] );
memset( f , -1 , sizeof( f ) );
cout << dp( 1 , 1 , 1 , 1 , 1 , 1 ) << endl;
return 0;
}
丑陋的

记录信息
评测状态 Accepted
题目 P1143 三取方格数
递交时间 2015-07-30 21:40:39
代码语言 C++
评测机 VijosEx
消耗时间 120 ms
消耗内存 444288 KiB
评测时间 2015-07-30 21:40:55
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 444284 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 444288 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 444288 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 444288 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 444284 KiB, score = 10
Accepted, time = 120 ms, mem = 444288 KiB, score = 100
#include <iostream>
#include <stdio.h>
using namespace std;
int f[22][22][22][22][22][22];
int map[30][30];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
for(int a=1;a<=n;a++)
for(int b=1;b<=n;b++)
for(int c=a;c<=n;c++)
for(int d=c;d<=n;d++)
{
f[a][b][c][a+b-c][d][a+b-d]=max (max (max(f[a-1][b][c-1][a+b-c][d-1][a+b-d] , f[a-1][b][c-1][a+b-c][d][a+b-d-1]) ,max(f[a][b-1][c-1][a+b-c][d-1][a+b-d],f[a][b-1][c-1][a+b-c][d][a+b-d-1])),max(max(f[a-1][b][c][a+b-c-1][d-1][a+b-d],f[a-1][b][c][a+b-c-1][d][a+b-d-1]),max(f[a][b-1][c][a+b-c-1][d-1][a+b-d],f[a][b-1][c][a+b-c-1][d][a+b-d-1])))+map[a][b]+map[c][a+b-c]+map[d][a+b-d];
if(a==c)f[a][b][c][a+b-c][d][a+b-d]-=map[a][b];
if(c==d)f[a][b][c][a+b-c][d][a+b-d]-=map[c][a+b-c];
}
printf("%d",f[n][n][n][n][n][n]);

}

大神不要笑我代码丑。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=30;
int k[maxn][maxn];
int f[maxn*2][maxn][maxn][maxn];
int numh;
int main()
{
scanf("%d",&numh);
for(int i=1;i<=numh;i++)
for(int j=1;j<=numh;j++)
scanf("%d",&k[i][j]);
for(int m=2;m<=numh+numh;m++)
for(int i=1;i<min(m,numh+1);i++)
for(int j=1;j<min(m,numh+1);j++)
for(int l=1;l<min(m,numh+1);l++)
{
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i][j][l]);
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i-1][j][l]);
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i][j-1][l]);
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i][j][l-1]);
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i-1][j-1][l]);

f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i-1][j][l-1]);

f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i][j-1][l-1]);
f[m][i][j][l]=max(f[m][i][j][l],f[m-1][i-1][j-1][l-1]);
f[m][i][j][l]+=k[i][m-i]+k[j][m-j]+k[l][m-l];
if(i==j)f[m][i][j][l]-=k[i][m-i];
if(i==l)f[m][i][j][l]-=k[i][m-i];
if(l==j)f[m][i][j][l]-=k[l][m-l];
if(i==j&&i==l&&l==j)f[m][i][j][l]+=k[l][m-l];
}
printf("%d\n",f[numh+numh][numh][numh][numh]);
return 0;
}

#include <iostream>
using namespace std;
int a[21][21],f[52][22][22][22];
int n;
int main(){
cin>>n;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
cin>>a[i][j];
for(int i=1; i<=2*n-1; ++i){
for(int j=1; j<=min(i,n); ++j){
for(int k=1; k<=min(i,n); ++k){
for(int x=1; x<=min(i,n); ++x){
int c=0;
if(j==k&&k==x) c=a[j][i+1-j];
else if(j==k) c=a[j][i+1-j]+a[x][i+1-x];
else if(j==x) c=a[j][i+1-j]+a[k][i+1-k];
else if(x==k) c=a[x][i+1-x]+a[j][i+1-j];
else c=a[x][i+1-x]+a[j][i+1-j]+a[k][i+1-k];
for(int q=0; q<=1; ++q)
for(int w=0; w<=1; ++w)
for(int e=0; e<=1; ++e)
f[i][j][k][x]=max(f[i][j][k][x],f[i-1][j-q][k-w][x-e]+c);
}
}
}
}
cout<<f[2*n-1][n][n][n]<<endl;
}

四维DP过了，类似传纸条

水题，不过时间比较丑，c++的高维数组的下标访问比较慢。。
代码奉上：
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn=25;
const int maxm=50;

int f[maxn][maxn][maxn][maxm];
int a[maxn][maxn];
int n,m;

int main()
{
cin>>n;
int i,j,k,l;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
m=n+n-1;
for(l=1;l<=m;l++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
f[i][j][k][l]=max( f[i][j][k][l-1],max(f[i][j][k-1][l-1],max(f[i-1][j][k][l-1],max(f[i][j-1][k][l-1],max(f[i-1][j-1][k][l-1],max(f[i-1][j][k-1][l-1],max(f[i][j-1][k-1][l-1],f[i-1][j-1][k-1][l-1])))))));
if(i==j)
{
if(i==k)
{
f[i][j][k][l]+=a[i][l-i+1];
}
else
{
f[i][j][k][l]+=(a[j][l-j+1]+a[k][l-k+1]);
}
}
else if(j==k)
{
f[i][j][k][l]+=(a[i][l-i+1]+a[k][l-k+1]);
}
else if(i==k)
{
f[i][j][k][l]+=(a[j][l-j+1]+a[k][l-k+1]);
}
else
{
f[i][j][k][l]+=(a[i][l-i+1]+a[j][l-j+1]+a[k][l-k+1]);
}
}
}
}
}
cout<<f[n][n][n][m]<<endl;
return 0;
}

cin>>n;
erep(i,1,n)
erep(j,1,n)
cin>>g[i][j];

f[1][1][1][1]=g[1][1];
erep(l,2,2*n-1){
erep(i1,1,min(l,n)){
erep(i2,1,min(l,n)){
erep(i3,1,min(l,n)){
f[l][i1][i2][i3]=max8(
f[l-1][i1][i2][i3],
f[l-1][i1][i2][i3-1],
f[l-1][i1][i2-1][i3],
f[l-1][i1][i2-1][i3-1],
f[l-1][i1-1][i2][i3],
f[l-1][i1-1][i2][i3-1],
f[l-1][i1-1][i2-1][i3],
f[l-1][i1-1][i2-1][i3-1]
);
int add=0;
add+=g[i1][l+1-i1]+g[i2][l+1-i2]+g[i3][l+1-i3];
if(i1==i2)
add-=g[i1][l+1-i1];
if(i2==i3)
add-=g[i2][l+1-i2];
if(i3==i1)
add-=g[i3][l+1-i3];
if(i1==i2 && i2==i3)
add+=g[i1][l+1-i1];
f[l][i1][i2][i3]+=add;
}
}
}
}
cout<<f[2*n-1][n][n][n]<<endl;

一个重要结论:
*如果某两条路径中有重复的方格,那么一定是在同一步走到他们的
有了这个结论每一个格子的重复取数字的问题就很好处理了

var
n,i,j,k,i1,i2,i3,ans:longint;
f:array[0..201,0..201,0..201] of longint;
mp:array[0..201,0..201] of longint;
function max(a,b,c,d,e,f,g,h:longint):longint;
begin
max:=a;
if b>max then max:=b;
if c>max then max:=c;
if d>max then max:=d;
if e>max then max:=e;
if f>max then max:=f;
if g>max then max:=g;
if h>max then max:=h;
end;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
read(mp[i,j]);
readln;
end;
for k:=3 to 2*n-3 do
for i1:=k-2 downto 1 do
for i2:=k-1 downto i1+1 do
for i3:=k downto i2+1 do
f[i1,i2,i3]:=max(f[i1,i2,i3],
f[i1,i2-1,i3-1],
f[i1,i2,i3-1],
f[i1,i2-1,i3],
f[i1-1,i2,i3],
f[i1-1,i2,i3-1],
f[i1-1,i2-1,i3],
f[i1-1,i2-1,i3-1])+mp[i1,k+1-i1]+mp[i2,k+1-i2]+mp[i3,k+1-i3];
ans:=f[n-2,n-1,n]+mp[1,1]+mp[2,1]+mp[1,2]+mp[n,n]+mp[n,n-1]+mp[n-1,n];
writeln(ans);
end.
把正方形顺时针转45度，可得到正倒两个金字塔形的结构，按金字塔的每一层推，下一层只跟上一层有关系
如 1
1 1
1 1 1
1 1 1 1
1 1 1
1 1
1

无语的直接打了个四维DP，直接递推解决，慢死了。。。
VijosEx via JudgeDaemon2/13.6.5.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 46 ms, mem = 49376 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 49372 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 49368 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 49368 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 49372 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 49372 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 49376 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 49372 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 49376 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 49368 KiB, score = 10
Accepted, time = 385 ms, mem = 49376 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 50

int f[MAXN+MAXN][MAXN][MAXN][MAXN];
int m[MAXN][MAXN];
int n;

int va(int k,int i,int j,int h){
int rec=0;
rec+=m[i][k-i+1];
if (j!=i){
rec+=m[j][k-j+1];
}
if (h!=i&&h!=j){
rec+=m[h][k-h+1];
}
return rec;
}

int main(){
scanf("%d",&n);
memset(m,0,sizeof(m));
for (int i=0;i++<n;){
for (int j=0;j++<n;){
scanf("%d",&m[i][j]);
}
}
memset(f,0,sizeof(f));
f[1][1][1][1]=m[1][1];
for (int k=0;k++<n+n-2;){
for (int i=0;i++<n;){
for (int j=0;j++<n;){
for (int h=0;h++<n;){
if (f[k][i][j][h]){
f[k+1][i][j][h]=max(f[k+1][i][j][h],f[k][i][j][h]+va(k+1,i,j,h));
f[k+1][i][j][h+1]=max(f[k+1][i][j][h+1],f[k][i][j][h]+va(k+1,i,j,h+1));
f[k+1][i][j+1][h]=max(f[k+1][i][j+1][h],f[k][i][j][h]+va(k+1,i,j+1,h));
f[k+1][i][j+1][h+1]=max(f[k+1][i][j+1][h+1],f[k][i][j][h]+va(k+1,i,j+1,h+1));
f[k+1][i+1][j][h]=max(f[k+1][i+1][j][h],f[k][i][j][h]+va(k+1,i+1,j,h));
f[k+1][i+1][j][h+1]=max(f[k+1][i+1][j][h+1],f[k][i][j][h]+va(k+1,i+1,j,h+1));
f[k+1][i+1][j+1][h]=max(f[k+1][i+1][j+1][h],f[k][i][j][h]+va(k+1,i+1,j+1,h));
f[k+1][i+1][j+1][h+1]=max(f[k+1][i+1][j+1][h+1],f[k][i][j][h]+va(k+1,i+1,j+1,h+1));
}
}
}
}
}
printf("%d\n",f[n+n-1][n][n][n]);
return 0;
}

题目分析：
这一题目乍一眼看上去跟1493题目类似，1493四位dp暴力可过，但是这一题6维暴力的话不是超时就是超内存。于是思考一下。由于移动的特殊性，只能向两个方向进行移动即下和右，因此这种从（1,1）移动至（n,n）的步数是相同的，即2*n-2步。那么对于第l步当i（纵坐标）唯一确定时，其对应的横坐标也必唯一确定。
因此得到状态转移方程 f(l,i1,i2,i3) = max( f(l-1,i1,i2,i3),
f(l-1,i1,i2,i3-1),
f(l-1,i1,i2-1,i3),
f(l-1,i1,i2-1,i3-1),
f(l-1,i1-1,i2,i3),
f(l-1,i1-1,i2,i3-1),
f(l1-1,i1-1,i2-1,i3),
f(l-1,i1-1,i2-1,i3-1)
)

之后需要做的事情就是对每一个格子的重复取数字的问题，详见代码如下：
###Block code
#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 21;

int map[MAXN][MAXN];

int dp[2*MAXN][MAXN][MAXN][MAXN];

int n;

int MAX(int a1,int a2,int a3, int a4,int a5,int a6,int a7,int a8){
int t;
if ( a1 <= a2 ) {
t = a2;
}else {
t = a1;
}
if ( t <= a3 ) t = a3;
if ( t <= a4 ) t = a4;
if ( t <= a5 ) t = a5;
if ( t <= a6 ) t = a6;
if ( t <= a7 ) t = a7;
if ( t <= a8 ) t = a8;
return t;
}

int main(){
int i,j,l,i1,i2,i3;
cin>>n;

for ( i = 1; i <= n; i++ ){
for ( j = 1; j <= n; j++ ){
cin>>map[i][j];
}
}

for ( l = 1; l <= 2*n-2; l++ ){
for ( i1 = 1; i1 <= l+1; i1++ ){
for( i2 = 1; i2 <= l+1; i2++ ){
for( i3 = 1; i3 <= l+1; i3++ ){
if ( ( (i1!=i2) || (i2!=i3) || (i1!=i2) )||
((i1==1)&&(i2==1)&&(i3==1))||
((i1==n)&&(i2==n)&&(i3==n)) ){
dp[l][i1][i2][i3] = MAX(
dp[l-1][i1][i2][i3],
dp[l-1][i1][i2][i3-1],
dp[l-1][i1][i2-1][i3],
dp[l-1][i1][i2-1][i3-1],
dp[l-1][i1-1][i2][i3],
dp[l-1][i1-1][i2][i3-1],
dp[l-1][i1-1][i2-1][i3],
dp[l-1][i1-1][i2-1][i3-1]
);
dp[l][i1][i2][i3] += map[i1][l-i1+2]
+map[i2][l-i2+2]
+map[i3][l-i3+2];
if ( i1 == i2 ) dp[l][i1][i2][i3] -= map[i1][l-i1+2]; //重复计算的减去
if ( i3 == i2 ) dp[l][i1][i2][i3] -= map[i2][l-i2+2];//重复计算的减去
if ( i1 == i3 ) dp[l][i1][i2][i3] -= map[i1][l-i1+2];//重复计算的减去
}
}
}
}
}
cout<<dp[2*n-2][n][n][n]+map[n][n]+map[1][1]<<endl;//[1][1]和[n][n]被减去了三次需要加回来
}

编译通过... 

├ 测试数据 01：答案正确... (0ms, 2400KB) 

├ 测试数据 02：答案正确... (0ms, 2400KB) 

├ 测试数据 03：答案正确... (0ms, 2400KB) 

├ 测试数据 04：答案正确... (0ms, 2400KB) 

├ 测试数据 05：答案正确... (0ms, 2400KB) 

├ 测试数据 06：答案正确... (0ms, 2400KB) 

├ 测试数据 07：答案正确... (0ms, 2400KB) 

├ 测试数据 08：答案正确... (0ms, 2400KB) 

├ 测试数据 09：答案正确... (0ms, 2400KB) 

├ 测试数据 10：答案正确... (0ms, 2400KB) 

多进程DP  F表示第I步第一个点在（X1，i-x1） 第二个点在（x2，i-x2）第三个点在（x3，i-x3）

#include

#include

#include

#include

using namespace std;

int a[30][30],f[70][25][25][25];

int g[8][3]={{-1,-1,-1},{-1,-1,0},{-1,0,-1},{0,-1,-1},

{0,0,-1},{0,-1,0},{-1,0,0},{0,0,0}};

int n;

int main()

{

int i,j,k,o,p,q,x,l1,l2,l3;

freopen("in.txt","r",stdin);

freopen("out.txt","w",stdout);

scanf("%d",&n);

for (i=1;i

#include

#include

using namespace std;

long int f[21][21][21];

int data[21][21];

int N,ans=0;

int maxx(int a1,int a2,int a3,int a4,int a5,int a6,int a7,int a8)

{

int t;

t=a1;

if(a2>t) t=a2;

if(a3>t) t=a3;

if(a4>t) t=a4;

if(a5>t) t=a5;

if(a6>t) t=a6;

if(a7>t) t=a7;

if(a8>t) t=a8;

return t;

}

int main()

{

memset(data,0,sizeof(data));

memset(f,0,sizeof(f));

cin>>N;

for(int i=1;idata[i][j];

ans=data[1][1]+data[1][2]+data[2][1]+data[N][N]+data[N-1][N]+data[N][N-1];

for (int i=3;i=1;j--)

for(int k=i-1;k>j;k--)

for(int l=i;l>k;l--)

{

f[j][k][l]=maxx(f[j][k][l],

f[j-1][k][l],

f[j][k-1][l],

f[j][k][l-1],

f[j-1][k-1][l],

f[j-1][k][l-1],

f[j][k-1][l-1],

f[j-1][k-1][l-1])

+data[j]

+data[k]

+data[l];

}

ans+=f[N-2][N-1][N];

cout

用我们大牛的讲法(跟LX有些大牛差不多):

将方格顺时针旋转45°,

将每一行上的点看做一层

发现步数一样的时候到达的"层数"也是一样的

然后先确定层数,(第一循环)(看了题解后发现可以省去这个维度)

再确定第一条路径的纵坐标i(第二循环,从原方格的第N-2个纵坐标到1...N,N-1至少要给另外两个路径走)

第二路径纵坐标j(第三循环,从N-1条边搜索到i+1)

第三路径纵坐标k(第四循环,第N条到第二路径边界j+1)

路径不重合;

O(N^4)...

不断更新F的最优解;更新完后加上三个新增坐标点的权值;(其实不加上也可以,将循环

最后输出F[N-2，N-1，N]加上前面被忽略的点(必定重合部分)的值(如果你直接从第三层搜索起,因为层数>3且层数不在倒数2层时保证路径不重合);

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我用的是六维 呵呵 一次AC哦！

var

n,i,j,k,ii,jj,kk,k1,k2,k3,p:integer;

w,r:longint;

f:array[0..20,0..20,0..20,0..20,0..20,0..20]of longint;

q:array[0..20,0..20,0..20]of boolean;

a:array[0..20,0..20]of byte;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a);

f[1,1,1,1,1,1]:=a[1,1];

for p:=3 to n*n do

begin

fillchar(q,sizeof(q),true);

for i:=1 to n do

for j:=1 to n do

for k:=1 to n do

if q then

if (ij)or(ik)or(jk) then

begin

ii:=p-i; jj:=p-j; kk:=p-k;

if (ii>0)and(jj>0)and(kk>0)and(ii

一次AC。。。

F表示第I步，横坐标为X，Y，Z

8种情况讨论即可

最后一次NOIP了。。。也许是VJ上AC的最后一题了。。。好怀念

加油！

自写的，数组只开到了20就行了；

program v1;

var k,i1,i2,i3,n,i,j:integer;

f:array[0..20,0..20,0..20]of integer;

w:array[1..20,1..20]of integer;

function max(a,b,c,d,e,f,g,h:integer):integer;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

if d>max then max:=d;

if e>max then max:=e;

if f>max then max:=f;

if g>max then max:=g;

if h>max then max:=h;

end;

begin

readln(n);fillchar(w,sizeof(w),0);

for i:=1 to n do

begin

for j:=1 to n do read(w);

readln;

end;

fillchar(f,sizeof(f),0);

f[1,1,1]:=w[1,1]+w[2,1];f[2,2,2]:=w[1,1]+w[1,2];

i:=w[1,1]+w[1,2]+w[2,1];for i1:=1 to 2 do for i2:=1 to 2 do for i3:=1 to 2 do f[i1,i2,i3]:=i; for k:=3 to 2*n-3 do

begin if k>n then i:=n else i:=k;

for i1:=i downto 3 do

for i2:=i1-1 downto 2 do

for i3:=i2-1 downto 1 do

f[i1,i2,i3]:=max(f[i1-1,i2-1,i3-1],

f[i1-1,i2-1,i3],

f[i1,i2-1,i3-1],

f[i1-1,i2,i3-1],

f[i1-1,i2,i3],

f[i1,i2-1,i3],

f[i1,i2,i3-1],

f[i1,i2,i3])+w[i1,k+1-i1]+w[i2,k+1-i2]+w[i3,k+1-i3];

end;

f[n,n,n]:=f[n,n-1,n-2]+w[n,n-1]+w[n-1,n]+w[n,n];

write(f[n,n,n]);

end.

优化1：由于第i阶段由i-1阶段推来，则可将i省略，但递推要用downto

优化2：规定t1>t2>t3则可以避免对三进程的位置是否重叠进行讨论。

不好意思贴一下抄来的程序，很赞

var

f : array[0..200,0..200,0..200]of longint;

map : array[0..200,0..200]of longint;

i, j, l, r, m, n, ans : longint;

function max(a,b,c,d,z,x,y,v:longint):longint;

　　　　begin

　　　　　　max := a;

　　　　　　if max < b then max := b;

　　　　　　if max < c then max := c;

　　　　　　if max < d then max := d;

　　　　　　if max < z then max := z;

　　　　　　if max < x then max := x;

　　　　　　if max < y then max := y;

　　　　　　if max < v then max := v;

　　　　end;

begin

　　 readln(n);

　　 for i := 1 to n do

　　 for j := 1 to n do read(map);

　　 fillchar(f,sizeof(f),0);

　　 for i := 3 to n*2-3 do

　　 for j := i-2 downto 1 do

　　 for l := i-1 downto j+1 do

　　　　for r := i downto l+1 do

　　　　 f[j,l,r] := max(f[j,l,r],

　　　　　　　　　　　　 f[j,l-1,r-1],

　　　　　　　　　　　　 f[j,l,r-1],

　　　　　　　　　　　　 f[j,l-1,r],

　　　　　　　　　　　　 f[j-1,l-1,r-1],

　　　　　　　　　　　　 f[j-1,l,r],

　　　　　　　　　　　　 f[j-1,l-1,r],

　　　　　　　　　　　　 f[j-1,l,r-1])+map+map+map;

　　 ans := f[n-2,n-1,n]+map[1,1]+map[1,2]+map[2,1]+map[n,n]+map[n,n-1]+map[n-1,n];

　　 writeln(ans);

end.