?

題目傳送門

1 /* 2 題意：抽象一點就是給兩個矩陣，重疊的(就是兩者選擇其一)，兩種鋪路：從右到左和從下到上，中途不能轉彎， 3 到達邊界后把沿途路上的權值相加求和使最大 4 DP：這是道遞推題，首先我題目看了老半天，看懂后寫出前綴和又不知道該如何定義狀態好，寫不出狀態轉移方程，太弱了。 5 dp[i][j]表示以(i, j)為右下角時求得的最大值，狀態轉移方程：dp[i][j] = max (dp[i-1][j] + sum1[i][j], dp[i][j-1] + sum2[i][j]); sum1表示列的前綴，sum2表示行的前綴 6 */ 7 /************************************************ 8 * Author :Running_Time 9 * Created Time :2015-8-9 10:18:37 10 * File Name :UVA_1366.cpp 11 ************************************************/ 12 13 #include <cstdio> 14 #include <algorithm> 15 #include <iostream> 16 #include <sstream> 17 #include <cstring> 18 #include <cmath> 19 #include <string> 20 #include <vector> 21 #include <queue> 22 #include <deque> 23 #include <stack> 24 #include <list> 25 #include <map> 26 #include <set> 27 #include <bitset> 28 #include <cstdlib> 29 #include <ctime> 30 using namespace std; 31 32 #define lson l, mid, rt << 1 33 #define rson mid + 1, r, rt << 1 | 1 34 typedef long long ll; 35 const int MAXN = 5e2 + 10; 36 const int INF = 0x3f3f3f3f; 37 const int MOD = 1e9 + 7; 38 int a[MAXN][MAXN], b[MAXN][MAXN]; 39 int sum1[MAXN][MAXN], sum2[MAXN][MAXN]; 40 int dp[MAXN][MAXN]; 41 42 int main(void) { //UVA 1366 Martian Mining 43 int n, m; 44 while (scanf ("%d%d", &n, &m) == 2) { 45 if (!n && !m) break; 46 memset (sum1, 0, sizeof (sum1)); 47 for (int i=1; i<=n; ++i) { 48 for (int j=1; j<=m; ++j) { 49 scanf ("%d", &a[i][j]); sum1[i][j] = sum1[i][j-1] + a[i][j]; 50 } 51 } 52 memset (sum2, 0, sizeof (sum2)); 53 for (int i=1; i<=n; ++i) { 54 for (int j=1; j<=m; ++j) { 55 scanf ("%d", &b[i][j]); sum2[i][j] = sum2[i-1][j] + b[i][j]; 56 } 57 } 58 memset (dp, 0, sizeof (dp)); 59 for (int i=1; i<=n; ++i) { 60 for (int j=1; j<=m; ++j) { 61 dp[i][j] = max (dp[i-1][j] + sum1[i][j], dp[i][j-1] + sum2[i][j]); 62 } 63 } 64 printf ("%d\n", dp[n][m]); 65 } 66 67 return 0; 68 }

?

轉載于:https://www.cnblogs.com/Running-Time/p/4714801.html

總結

以上是生活随笔為你收集整理的递推DP UVA 1366 Martian Mining的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。