SDNUOJ——1032.機器人

Description

SYC喜歡宅在家裡，但又不喜歡清理垃圾，有一天實在看不下去了，就把好友ZZK和LG叫來幫忙。沒想到他倆更懶，把各自的機器人帶過來了，當然，大家都不願意為這兩台機器人設計程式，是以請你來幫忙。

為了運算的簡單，我們将SYC的屋子看做NM的矩陣，在矩陣的每一個坐标上都可能有不同數量的垃圾。已知開始時這兩個機器人都放在矩陣的左上角，兩個機器人每次都隻能向右或向下走一步，而且不能向回走，也不能走另一個機器人走過的坐标。現在請你幫忙，計算這兩個機器人都走到右下角時打掃垃圾的最大數量。

Input

第一行有兩個整數N和M，分别表示SYC家占地N行M列。1<=N,M<=50。

接下來有N行，每行有M個資料，表示NM的矩陣，每行各個數字使用空格分隔。矩陣第i行j列的數字表示該處垃圾的個數(不超過1000)。

Output

輸出打掃垃圾的最大數量

Sample Input

3 3

0 9 9

6 1 8

2 3 0

Sample Output

37

正确思路：思維dp

錯誤思路：暴力搜尋。。。

//#include<bits/stdc++.h>
#include  <stdio.h>
#include <iostream>
#include<algorithm>
//#include      <map>
//#include      <set>
//#include   <vector>
//#include    <queue>
//#include    <stack>
#include <stdlib.h>
#include  <cstring>
#include <string.h>
#include   <string>
#include   <math.h>
using namespace std;
typedef long long ll;
#define MAXN 55
#define INF 0x3f3f3f3f//将近ll類型最大數的一半，而且乘2不會爆ll

int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            scanf("%d", &a[i][j]);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            for(int k=1; k<i; ++k)
            {
                int l = i+j-k;	//i+j = k+l
                dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1]))+ a[i][j] + a[k][l];
            }
    cout << dp[n][m-1][n-1][m] << '\n';
    return 0;
}