40分 记忆化搜索 思路清晰但没过
查看原帖
40分 记忆化搜索 思路清晰但没过
465029
Specter_LiZN楼主2024/9/15 11:52
#include <bits/stdc++.h>
#define f(i,a,b) for (int i=a;i<=b;i++)
#define ArrayOut(a,b,outArray,beg,wid) for (int i=beg;i<=a;i++){ for (int j=beg;j<=b;j++) cout<<setw(wid)<<outArray[i][j]; cout<<'\n';}
#define Shion cout << "Shion is too poor to print that." << endl
const int Miku=0x3f3f3f3f;
using namespace std;

int n,m,in[205][205],mem[205][205];

int dfs(int x,int y) {
	if(mem[x][y])
    return mem[x][y];//memory search
	if(x<1||y<1||x>m||y>n)
    return 0;//finish
  int sola=dfs(x-1,y)+in[x-1][y];
  int solb=dfs(x-1,y-1)+in[x-1][y-1];
  int solc=dfs(x-1,y+1)+in[x-1][y+1];
	return mem[x][y]=max(sola,max(solb,solc));
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  f(i,1,n)
    f(j,1,m)
      cin>>in[i][j];
  // ArrayOut(n,m,in,1,2);
  int staa=dfs(m,n/2)+in[m][n/2];    //left
  int stab=dfs(m,n/2+1)+in[m][n/2+1];//straight
  int stac=dfs(m,n/2+2)+in[m][n/2+2];//right
  cout<<max(staa,max(stab,stac));
  return 0;
  Shion;
}
2024/9/15 11:52
加载中...