題目?

?

思路

首先，這道題乍一看，應該可以用搜索來做。

但是，搜索會不會超時間限制呢？

為了防止時間超限,我們可以換一種做法。

先創立兩個二維數組，一個是輸入的數組a，一個是數組b。

假設?i 行 j 列的數是 a [ i ] [ j ]，和b?[ i ] [ j ]

輸入的時候判斷：如果?a [ i ] [ j ]<300,那么?a [ i ] [ j ] =?a [ i ] [ j ] /2。

然后，b?[ i ] [ j ] =?a [ i ] [ j ].

如果學過小學奧數：標數法

那么，你會很好理解：

一排一排、從左到右的去處理：

走到 a [ i ] [ j ] 這處銀子時，得到的銀子總量為 a?[ i ] [ j ] + max(?b?[ i - 1 ] [ j ] , b?[ i ] [ j - 1 ]).將這個數存在?b?[ i ] [ j ]中。

最后，只要輸出?b?[ n?] [ m?] 就好了

相信標數法你們都學過，因為它很簡單，所以這里就不多解釋這樣寫的原因了。

AC代碼：

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[110][110];
int b[110][110];
int main()
{cin>>n>>m;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){cin>>a[i][j];if(a[i][j]<300) a[i][j] /= 2;b[i][j] = a[i][j];}}for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){b[i][j] += max(b[i-1][j],b[i][j-1]);}}cout<<b[n][m];return 0;
}