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

``````评测结果

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 条评论

• @ 2016-11-12 20:21:35

暴力出奇迹！

• @ 2016-11-12 20:55:39

然而并没有出奇迹

• @ 2016-11-12 21:13:55

你看一下第1445题的题目，很逗的^.^

• @ 2016-11-12 21:17:44

排序

• @ 2016-11-12 21:50:14

• @ 2016-11-12 22:34:28

doge

• 1

ID
1493

5

6702

2504

37%

8