我一蒟蒻,遇到dp只能爆搜

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 516 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
测试数据 #7: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 512 KiB, score = 0
TimeLimitExceeded, time = 7105 ms, mem = 520 KiB, score = 30
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m,g[51][51],Max = -1000000000;
bool vis[51][51];
inline void dfs2(int x,int y,int tot) {
  if (x == 1 && y == 1) {
    Max = max(Max,tot);
    return;
  }
  if (x-1 >= 1 && !vis[x-1][y]) {
    vis[x-1][y] = true;
    dfs2(x-1,y,tot+g[x-1][y]);
    vis[x-1][y] = false;
  }
  if (y-1 >= 1 && !vis[x][y-1]) {
    vis[x][y-1] = true;
    dfs2(x,y-1,tot+g[x][y-1]);
    vis[x][y-1] = false;
  }
}
inline void dfs1(int x,int y,int tot) {
  if (x == n && y == m) {
    dfs2(n,m,tot);
    return;
  }
  if (x+1 <= n && !vis[x+1][y]) {
    vis[x+1][y] = true;
    dfs1(x+1,y,tot+g[x+1][y]);
    vis[x+1][y] = false;
  }
  if (y+1 <= m && !vis[x][y+1]) {
    vis[x][y+1] = true;
    dfs1(x,y+1,tot+g[x][y+1]);
    vis[x][y+1] = false;
  }
}
int main() {
  //freopen("message.in","r",stdin);
  //freopen("message.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i = 1;i <= n;i++)
   for (int j = 1;j <= m;j++) scanf("%d",&g[i][j]);
  memset(vis,false,sizeof(vis));
  dfs1(1,1,0);
  printf("%d",Max);
  return 0;
}

1 条评论

  • 1

信息

ID
1493
难度
5
分类
动态规划 点击显示
标签
递交数
6702
已通过
2504
通过率
37%
被复制
9
上传者