RT,蒟蒻作死想用记忆化写,结果WA20
查看原帖
RT,蒟蒻作死想用记忆化写,结果WA20
248407
暴力出奇迹NB楼主2020/10/27 00:15
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,m,a[55][55],t[55][55],f[55][55][55][55];
int dx1[10]={0,0,0,1,1},dy1[10]={0,1,1,0,0},dx2[10]={0,0,-1,0,-1},dy2[10]={0,-1,0,-1,0};
int dfs(int x1,int y1,int x2,int y2){
	if(f[x1][y1][x2][y2]!=-1)return f[x1][y1][x2][y2];
	if(x1==m&&y1==n&&x2==1&&y2==1)return 0;
	int tmp=0;
	for(int i=1;i<=4;i++){
		int xx1=x1+dx1[i],yy1=y1+dy1[i],xx2=x2+dx2[i],yy2=y2+dy2[i];
		if(xx1!=xx2||yy1!=yy2) 
			if(t[xx1][yy1]==0&&t[xx2][yy2]==0&&xx1>=1&&xx1<=m&&xx2>=1&&xx2<=m&&yy1>=1&&yy1<=n&&yy2>=1&&yy2<=n){
				t[xx1][yy1]=t[xx2][yy2]=1;
				tmp=max(tmp,dfs(xx1,yy1,xx2,yy2)+a[xx1][yy1]+a[xx2][yy2]);
				t[xx1][yy1]=t[xx2][yy2]=0;	
			}		
	}	
	return f[x1][y1][x2][y2]=tmp;	
}
int main(){
	scanf("%d %d",&m,&n);
	for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
	memset(f,-1,sizeof(f));
	printf("%d",dfs(1,1,m,n));
	return 0;
}
2020/10/27 00:15
加载中...