資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究允許兩人在 C++ 中會面一次收集的最大點數
在本教程中，我們將討論一個程式，找出允許兩人會面一次收集的最大點數
為此，我們將得到一個包含點單元格的矩陣。我們的任務是找到兩人從兩個角落開始的路徑，這樣他們收集的最大點數。
示例
#include<bits/stdc++.h>
#define M 3
#define N 3
using namespace std;
int findMaxPoints(int A[][M]) {
//storing points
int P1S[M+1][N+1], P1E[M+1][N+1];
memset(P1S, 0, sizeof(P1S));
memset(P1E, 0, sizeof(P1E));
int P2S[M+1][N+1], P2E[M+1][N+1];
memset(P2S, 0, sizeof(P2S));
memset(P2E, 0, sizeof(P2E));
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
for (int i=N; i>=1; i--)
for (int j=M; j>=1; j--)
P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
for (int i=N; i>=1; i--)
for(int j=1; j<=M; j++)
P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
for (int i=1; i<=N; i++)
for (int j=M; j>=1; j--)
P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
int ans = 0;
for (int i=2; i<N; i++) {
for (int j=2; j<M; j++) {
int op1 = P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j];
int op2 = P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1];
ans = max(ans, max(op1, op2));
}
}
return ans;
}
int main() {
int A[][M] = {
{100, 100, 100},
{100, 1, 100},
{100, 100, 100}
};
cout << "Max Points : " << findMaxPoints(A);
return 0;
}輸出
Max Points : 800
更新於：09-9-2020
74 次瀏覽
廣告