今天來記錄一個簡單的DP題（我不是在水博客！）
1492: Problem D
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 312 Solved: 125
[Submit][Status][Web Board]
Description
Chieh最近在網上看到藍翔非常火熱，不知為什么他想到了一個問題，有一個n*m的矩陣
每一個小塊里有k個石頭，，現在挖掘機在左上角，挖掘機非常強大，，可以放無限的石頭
但是它只能往右或者往下移動，現在Chieh想知道最多的石頭從左上角到右下角，
Input
T 組數 T<=100
n m 1<=n. m<=1000
n行m個數 為石頭數量 0<=s<=1000
Output
對于每組測驗資料，輸出對應的答案，
Sample Input
2
1 1
1
4 3
1 3 4
11 32 4
11 32 11
44 21 41
Sample Output
1
138
題目讓我們找到挖掘機可挖掘的最大值，核心思想就是貪心演算法，具體點就是DP背包問題
這道題目很顯然是一個簡單的DP題目，我們只需要找到動態轉移方程即可，這里的動態轉移方程為dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) + a[i][j]，
以下為AC 代碼
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
typedef long long ll;
int a[maxn][maxn],dp[maxn][maxn];
int main(){
int n,m;
int T;
cin >> T;
while (T--) {
memset(dp, 0, sizeof dp);
memset(a, 0, sizeof a);
scanf("%d%d",&n,&m);
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j] = max(dp[i-1][j], dp[i][j-1])+a[i][j];
cout << dp[n][m] << endl;
}
}
return 0;
}
昨天經過高人指點，得到了一種更快的AC代碼，而且還省空間，其實a陣列的設定是沒有必要的，以下是AC代碼
#include<bits/stdc++.h>
using namespace std;
int dp[2][1005];
int main(){
int t,m,n,x,e;
cin >> t;
while(t--)
{
scanf("%d%d",&n,&m);
e = 0;
memset(dp, 0, sizeof dp);
for(int i=1;i<=n;i++)
{
e = 1- e;
for(int j=1;j<=m;j++){
cin >> x;
dp[e][j] = max(dp[1-e][j],dp[e][j-1]);
dp[e][j] += x;
}
}
cout << dp[e][m] << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264748.html
標籤：其他