Di chuyển - LCOJ: Luyện Code Online Judge

MOVE - Di chuyển

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một bàn cờ hình chữ nhật gồm ~m~ hàng và ~n~ cột. Mỗi ô trên bàn cờ này có ghi một giá trị nguyên. Xuất phát từ ô ~(1, 1)~, bạn cần di chuyển đến ô ~(m, n)~. Ở mỗi bước, bạn được di chuyển sang phải một ô hoặc xuống dưới một ô. Hãy tìm cách di chuyển để tổng giá trị của các ô trên đường đi là lớn nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~m~ và ~n\ (1 ≤ m, n ≤500)~;
~m~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên là giá trị các ô trên bàn cờ. Các ô này có giá trị tuyệt đối không quá ~10000~.

Output

In ra tổng giá trị lớn nhất tìm được.

Sample

Input #1

5 5
-9 -1 -3 6 -6
8 -3 3 -7 2
4 -3 1 -10 -9
-4 -8 -2 -3 -10
-7 7 5 4 3

Output #1

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

Code tham khảo (C++)

#include <bits/stdc++.h>
using namespace std;

#define MAX 670

int n, m;
int a[MAX][MAX];
int dp[MAX][MAX];

void init(void) {
    memset(dp, -0x3f, sizeof dp);
    dp[1][1] = a[1][1];
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i][j]), dp[i][j] = max(dp[i][j], dp[i][j - 1] + a[i][j]);
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>m>>n;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            cin>>a[i][j];
    init();
    cout<<dp[m][n];
    return 0;
}

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int m, n;
cin >> m >> n;

vector&lt;vector&lt;long long>> a(m+1, vector&lt;long long>(n+1));
vector&lt;vector&lt;long long>> dp(m+1, vector&lt;long long>(n+1, -1e18));

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        cin >> a[i][j];

dp[1][1] = a[1][1];

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (i > 1) dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i][j]);
        if (j > 1) dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i][j]);
    }
}

cout << dp[m][n];

}

-2

tdq đã bình luận lúc 1, Tháng 10, 2023, 13:15

ai giúp em với ạ làm bằng c++ nha

-1

BayAcc102 đã bình luận lúc 19, Tháng 2, 2024, 3:49

quy hoach dong

-2

NTA đã bình luận lúc 17, Tháng 11, 2023, 3:09

dùng quay lui nha em