比赛 防止颓废的小练习v0.4 评测结果 AAAAAAAAAA
题目名称 传纸条 最终得分 100
用户昵称 sxysxy 运行时间 1.423 s
代码语言 C++ 内存使用 35.23 MiB
提交时间 2016-10-25 08:47:41
显示代码纯文本
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. #define MAXN (55)
  7. int map[MAXN][MAXN];
  8. int dp[MAXN][MAXN][MAXN][MAXN];
  9.  
  10. int main()
  11. {
  12. freopen("message.in", "r", stdin);
  13. freopen("message.out", "w", stdout);
  14. int i,j,k,l;
  15. int n,m;
  16. cin >> m >> n;
  17. for(i = 1; i <= m; i++)
  18. for(j = 1; j <= n; j++)
  19. scanf("%d", &map[i][j]);
  20. for(i = 1; i <= m; i++)
  21. {
  22. for(j = 1; j <= n; j++)
  23. {
  24. for(k = 1; k <= m; k++)
  25. {
  26. for(l = 1; l <= n; l++)
  27. {
  28. dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k-1][l]);
  29. dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l-1]);
  30. dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k-1][l]);
  31. dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l-1]);
  32. dp[i][j][k][l] += map[i][j];
  33. if(i != k || j != l)
  34. dp[i][j][k][l] += map[k][l];
  35. }
  36. }
  37. }
  38. }
  39. cout << dp[m][n][m][n];
  40. return 0;
  41. }