#include<cstdio>
#include<algorithm>
#define MAXN 50 + 10
using namespace std;

int num[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];

int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d", &num[i][j]);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int k=1; k<=n; k++)
for(int l=1; l<=m; l++)
if((i != k || j != l) || (i == n && k == n && j == m && l == m))
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]))) + num[i][j] + num[k][l];
printf("%d", f[n][m][n][m]);
return 0;
}

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 356 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 356 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 352 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 356 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 356 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 352 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 352 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 356 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 352 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 356 KiB, score = 10

Accepted, time = 30 ms, mem = 356 KiB, score = 100

#include <cstdio>
#include <iostream>
using namespace std;
int m,n,a[101][101],f[101][101]={};
int main(){
int i,j,k,l,r;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++) scanf("%d",&a[i+j-1][i-j+n]);
f[n-1][n+1]=a[2][n-1]+a[2][n+1];
for(k=3;k<=m+n-2;k++){
l=max(1+k-n,1+n-k);
r=min(k+n-1,2*m+n-k-1);
for(i=l;i<r;i+=2)
for(j=i+2;j<=r;j+=2){
if(k+i-n!=1) f[i][j]=max(f[i][j],f[i-1][j-1]);
if(k-j-n!=1) f[i][j]=max(f[i][j],f[i+1][j+1]);
if(k+i-n!=1&&k-j-n!=1) f[i][j]=max(f[i][j],f[i-1][j+1]);
if(j-i!=2) f[i][j]=max(f[i][j],f[i+1][j-1]);
f[i][j]+=a[k][i]+a[k][j];
}
}
printf("%d",f[m-1][m+1]);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 1876 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1876 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1876 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1876 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1876 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1868 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1876 KiB, score = 10
Accepted, time = 30 ms, mem = 1876 KiB, score = 100

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=55;
int k[maxn][maxn];
int numh,numl;
int f[maxn*2][maxn][maxn]={0};
int main()
{
int a,b;
scanf("%d%d",&numh,&numl);
for(int i=1;i<=numh;i++)
for(int j=1;j<=numl;j++)
scanf("%d",&k[i][j]);
for(int r=1;r<=numh+numl;r++)
for(int i=1;i<=r;i++)
for(int j=1;j<=r;j++)
{
if(i-1!=j-1)
f[r][i][j]=max(f[r][i][j],f[r-1][i-1][j-1]+k[i][r-i]+k[j][r-j]);
if(i!=j-1)
f[r][i][j]=max(f[r][i][j],f[r-1][i][j-1]+k[i][r-i]+k[j][r-j]);
if(i-1!=j)
f[r][i][j]=max(f[r][i][j],f[r-1][i-1][j]+k[i][r-i]+k[j][r-j]);
if(i!=j)
f[r][i][j]=max(f[r][i][j],f[r-1][i][j]+k[i][r-i]+k[j][r-j]);
}
printf("%d\n",f[numh+numl][numh][numh]);
return 0;
}
代码略丑。。。

#include<iostream>
using namespace std;

int m,n,a[51][51],f[101][51][51];
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
f[1][1][1]=a[1][1];

for(int k=2;k<=n+m-1;k++)
for(int x=1;x<=min(m,k);x++)
for(int y=1;y<=min(k,m);y++)
{
if(x==y)
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
f[k][x][y]=max(f[k][x][y],f[k-1][x-i][y-j]+a[x][k-x+1]);
else
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
f[k][x][y]=max(f[k][x][y],f[k-1][x-i][y-j]+a[x][k-x+1]+a[y][k-y+1]);

}

cout<<f[m+n-1][m][m];
return 0;
}
完美ac

20行~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 51268 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 51276 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 51276 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 51276 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 51280 KiB, score = 10
Accepted, time = 60 ms, mem = 51280 KiB, score = 100
代码
#include<cstdio>
int n,m,val[60][60],res[60][60][60][60];
void MAX(int &i,int j){if (i<j) i=j;}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++) scanf("%d",&val[i][j]);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
for (int x=1; x<=n; x++)
if ( i+j-x && i<x ) {
int y=i+j-x;
MAX(res[i][j][x][y],res[i-1][j][x-1][y]);
MAX(res[i][j][x][y],res[i-1][j][x][y-1]);
MAX(res[i][j][x][y],res[i][j-1][x-1][y]);
MAX(res[i][j][x][y],res[i][j-1][x][y-1]);
res[i][j][x][y] += val[i][j] + val[x][y];

}
printf("%d",res[n-1][m][n][m-1]);
}

拆点+最大费用流
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 672 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 668 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 688 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 720 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 768 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 920 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1236 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1316 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1380 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 1368 KiB, score = 10
Accepted, time = 153 ms, mem = 1380 KiB, score = 100
略慢 当成有负权的ZKW费用流模版来写了
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>

using namespace std;

#define MAXN 51
#define MAXV MAXN*MAXN*2+10
#define inf 0x7fffffff

struct edge {
int t,f,c;
edge *pair,*next;
edge () {
pair=next=NULL;
}
} *head[MAXV];

void Add(int s,int t,int f,int c) {
edge *p=new(edge);
p->t=t;
p->f=f;
p->c=c;
p->next=head[s];
head[s]=p;
}

void AddEdge(int s,int t,int f,int c) {
Add(s,t,f,c);
Add(t,s,0,-c);
head[s]->pair=head[t];
head[t]->pair=head[s];
}

int w[MAXN][MAXN];
int n,m;
int v[MAXN][MAXN][2];
int S,T,V=0;

void INIT() {
scanf("%d%d",&n,&m);
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
scanf("%d",&w[i][j]);
}
}
memset(head,0,sizeof(head));
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
v[i][j][0]=++V;
v[i][j][1]=++V;
if ((i==1&&j==1)||(i==n&&j==m)) {
AddEdge(v[i][j][0],v[i][j][1],2,0);
} else AddEdge(v[i][j][0],v[i][j][1],1,-w[i][j]);
}
}
S=v[1][1][0];T=v[n][m][1];
for (int i=0;i++<n;) {
for (int j=0;j++<m;) {
if (i+1<=n) {
AddEdge(v[i][j][1],v[i+1][j][0],1,0);
}
if (j+1<=m) {
AddEdge(v[i][j][1],v[i][j+1][0],1,0);
}
}
}
}

int d[MAXV];
bool f[MAXV];
queue<int>Q;

void spfa() {
for (int i=0;i++<T;) d[i]=inf;
memset(f,true,sizeof(f));
d[S]=0;
while (!Q.empty()) Q.pop();
Q.push(S);
while (!Q.empty()) {
int v=Q.front();
Q.pop();
if (!f[v]) continue;
f[v]=false;
for (edge *p=head[v];p;p=p->next) {
if (p->f&&d[p->t]>d[v]+p->c) {
d[p->t]=d[v]+p->c;
f[p->t]=true;
Q.push(p->t);
}
}
}
}

int dist[MAXV],slack[MAXV];
int cost=0;

void dfs(int v) {
f[v]=false;
for (edge *p=head[v];p;p=p->next) {
if (p->f&&d[v]+p->c==d[p->t]&&f[p->t]) {
dist[p->t]=dist[v]-p->c;
dfs(p->t);
}
}
}

int aug(int v,int flow) {
if (v==T) {
cost+=flow*(dist[S]-dist[T]);
return flow;
}
f[v]=false;
int rec=0;
for (edge *p=head[v];p;p=p->next) {
if (p->f&&f[p->t]) {
if (dist[v]==dist[p->t]+p->c) {
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret,p->pair->f+=ret;
if ((rec+=ret)==flow) return flow;
} else slack[p->t]=min(slack[p->t],dist[p->t]-dist[v]+p->c);
}
}
return rec;
}

bool relabel() {
int delta=inf;
for (int i=0;i++<T;) {
if (f[i]) delta=min(delta,slack[i]);
}
if (delta==inf) return false;
for (int i=0;i++<T;) {
if (!f[i]) dist[i]+=delta;
}
return true;
}

void costflow() {
spfa();
memset(f,true,sizeof(f));
memset(dist,0,sizeof(dist));
dfs(S);
do {
for (int i=0;i++<T;) slack[i]=inf;
do {
memset(f,true,sizeof(f));
} while (aug(S,0x7fffffff));
} while (relabel());
}

int main() {
INIT();
costflow();
printf("%d\n",-cost);
return 0;
}

DP
上海红茶馆 - Windows Server 2012 via JudgeDaemon2/13.4.6.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1560 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1552 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1552 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1560 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1552 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1556 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1560 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1556 KiB, score = 10
Accepted, time = 30 ms, mem = 1560 KiB, score = 100
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 51

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

int main(){
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
for (int j=0;j++<m;){
scanf("%d",&a[i][j]);
}
}
for (int i=0;i<=n+m-1;i++){
for (int j=0;j++<n;){
for (int k=0;k++<n;){
f[i][j][k]=0;
}
}
}
f[0][1][1]=1;
for (int k=0;k++<n+m-2;){
for (int i=0;i++<n;){
for (int j=0;j++<n;){
if (i!=j){
if (f[k-1][i][j]) f[k][i][j]=f[k-1][i][j];
if (f[k-1][i-1][j]) f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j]);
if (f[k-1][i][j-1]) f[k][i][j]=max(f[k][i][j],f[k-1][i][j-1]);
if (f[k-1][i-1][j-1]) f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j-1]);
if (f[k][i][j]){
f[k][i][j]+=a[i][k+2-i];
f[k][i][j]+=a[j][k+2-j];
}
}
}
}
}
printf("%d\n",max(f[n+m-2][n-1][n],f[n+m-2][n][n-1])-1);
// system("pause");
return 0;
}

测试结果1: 通过本测试点|有效耗时640ms

测试结果2: 通过本测试点|有效耗时594ms

测试结果3: 通过本测试点|有效耗时578ms

测试结果4: 通过本测试点|有效耗时672ms

测试结果5: 通过本测试点|有效耗时579ms

测试结果6: 通过本测试点|有效耗时610ms

测试结果7: 通过本测试点|有效耗时640ms

测试结果8: 通过本测试点|有效耗时688ms

测试结果9: 通过本测试点|有效耗时640ms

测试结果10: 通过本测试点|有效耗时578ms

提交代码： view sourceprint?01.program strke;

02.var

03.

n,ans:longint;

04.

a:array[0..9] of longint;

05.procedure init;

06.begin

07.

08.end;

09.

10.procedure terminate;

11.begin

12.

close(input);

13.

close(output);

14.

halt;

15.end;

16.procedure readdata;

17.begin

18.

read(n);

19.end;

20.

21.procedure chuli(sum,i,j:longint);

22.var

23.

s1,s2,s3:string;

24.

x,total,ii,kk,jj:longint;

25.begin

26.

total:=0;

27.

str(sum,s1);str(i,s2);str(j,s3);

28.

ii:=1;jj:=1;kk:=1;

29.

while length(s1)0 do

30.

begin

31.

val(s1[ii],x);

32.

total:=total+a[x];

33.

delete(s1,ii,1);

34.

end;

35.

while length(s2)0 do

36.

begin

37.

val(s2[jj],x);

38.

total:=total+a[x];

39.

delete(s2,jj,1);

40.

end;

41.

while length(s3)0 do

42.

begin

43.

val(s3[kk],x);

44.

total:=total+a[x];

45.

delete(s3,kk,1);

46.

end;

47.

if total=n-4 then

48.

begin

49.

// writeln(sum,'=',i,'+',j);

50.

inc(ans);

51.

end;

52.end;

53.

54.procedure main;

55.var

56.

i,j,sum:longint;

57.begin

58.

a[0]:=6;a[1]:=2;a[2]:=5;a[3]:=5;a[4]:=4;

59.

a[5]:=5;a[6]:=6;a[7]:=3;a[8]:=7;a[9]:=6;

60.

sum:=0;ans:=0;

61.

for i:=0 to 712 do

62.

begin

63.

for j:=0 to 712 do

64.

begin

65.

sum:=i+j;

66.

chuli(sum,i,j);

67.

end;

68.

end;

69.

writeln(ans);

70.

//t1:=now-t1;

71.

// writeln(t1*86400:0:2);

72.end;

73.

75.begin

76.

init;

77.

readdata;

78.

main;

79.

terminate;

80.end.

既然4维可以过，又那么好理解。。干嘛改来改去。。

不会

帮帮忙，为什么在另一个是100，到这0？？？

var i,j,k,m,n:integer;

r:array[0..100,0..50,0..50]of integer;

s:array[0..50,0..50]of integer;

function max(a,b,c,d:integer):integer;

begin

if a>=b then max:=a else max:=b;

if c>max then max:=c;if d>max then max:=d;

end;

function min(a,b:integer):integer;

begin if a>=b then min:=b else min:=a;end;

begin

readln(m,n);fillchar(r,sizeof(r),0);

for i:=1 to m do for j:=1 to n do read(s);

for k:=1 to m+n-2 do

for j:=1 to min(m,k+1) do

for i:=j to min(m,k+1) do

if (i>j)or((i=m)and(j=m)and(k+2-i=n)and(k+2-j=n))then

begin

r[k,i,j]:=max(r[k-1,i,j],r[k-1,i,j-1],r[k-1,i-1,j],r[k-1,i-1,j-1]);

r[k,i,j]:=r[k,i,j]+s+s[j,k+2-j];

end;

writeln(r[m+n-2,m,m]);

end.

我无聊的说一句 ：网络流可过。。。。。。。

能不能帮我看看？

var n,m,i,j:longint;

f:array[1..50,1..50,1..50,1..50] of longint;

s:array[1..50,1..50] of longint;

procedure dg(a,b,c,d:longint);

begin

if (((a=n) and (b=m-1) and (c=n-1) and (d=m))

or ((c=n) and (d=m-1) and (a=n-1) and (b=m)))

and (f[a,b,c,d]>f[n,m,n,m])

then f[n,m,n,m]:=f[a,b,c,d];

if a

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

m,n,i,j,ii,jj,p:integer;

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

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

w:longint;

function max(a,b,c,d:longint):longint;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

if d>max then max:=d;

end;

begin

readln(m,n);

for i:=1 to m do

for j:=1 to n do

begin

read(a);

end;

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

for p:=3 to n*m do

begin

for i:=1 to m-1 do

for j:=i+1 to m do

begin

ii:=p-i;

jj:=p-j;

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

Program zhitiao;

Var

m,n,i,j,max:longint;

a:array[0..2500]of 0..100;

f:array[-100..2500,-100..2500]of longint;

Begin

readln(m,n);

for i:=1 to m do

for j:=1 to n do

read(a[(i-1)*n+j]);

for i:=2 to m*n do

for j:=2 to m*n do

begin

max:=0;

if (i mod n1)and(j mod n1)and(f>max)

then max:=f;

if (i mod n1) and (f>max) then max:=f;

if (j mod n1) and (f>max) then max:=f;

if f>max then max:=f;

if ij then max:=max+a[i]+a[j]

else max:=max+a[i];

if max>f then f:=max;

end;

writeln(f[m*n,m*n]);

End.

dfd

var

m,n,i1,j1,i2,j2,i,j,s:longint;

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

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

function max(a,b,c,d:longint):longint;

begin

if (a>=b) and (a>=c) and (a>=d) then max:=a;

if (a=c) and (b>=d) then max:=b;

if (c>=b) and (a=d) then max:=c;

if (d>=b) and (d>=c) and (a

program p1493(input,output);

var n,m,a,b,c,d,zz1,zz2:longint;

ab:array [0..51,0..51] of longint;

zhi:array [0..51,0..51,0..51,0..51] of longint;

begin

readln(m,n);

for a:=1 to m do

ab[a,0]:=0;

for b:=1 to n do

ab:=0;

for a:=1 to m do

begin

for b:=1 to n do

read(ab[a,b]);

end;

for a:=1 to m do

for b:=1 to n do

for c:=1 to m do

begin

d:=a+b-c;

if (d>0) and (a>c) and (bzhi[a-1,b,c,d-1]

then zz1:=zhi[a-1,b,c-1,d]

else zz1:=zhi[a-1,b,c,d-1];

if zhi[a,b-1,c-1,d]>zhi[a,b-1,c,d-1]

then zz2:=zhi[a,b-1,c-1,d]

else zz2:=zhi[a,b-1,c,d-1];

if zz1

#include

using namespace std;

int dp[53][53][53][53]={0};

int max(int,int,int,int);

int main()

{

int m,n,a[52][52],i1,i2,j1,j2;

cin>>m>>n;

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

dp[1][1][1][1]=a[1][1];

for(i1=1;i1