Code DPFLOWER - Khăn đỏ và bó hoa tặng bà chỉ được 50% số test

[linhmoi (lính mới)]

Đề bài

Trên đường từ nhà bé Khăn đỏ (trong truyện cô bé quàng khăn đỏ) đến nhà bà ngoại phải đi qua một khu rừng. Khu rừng hình chữ nhật được chia thành M hàng N cột, hàng được đánh số từ 1 đến M , cột được đánh số từ 1 đến N , ô ở hàng i , cột j được ký hiệu là ô (i,j) . Nhà bé khăn đỏ ở ô (1,1) còn nhà bà ngoại ở ô (M,N) .

Trên khu rừng, có một số ô có bông hoa, một số ô không có gì và một số ô có sói hung dữ mà ta không thể đi vào đó.

Ta quy ước những ô có số -1 là có sói, những ô có số 0 là không có gì và những ô có số nguyên dương là có bông hoa với độ đẹp là số nguyên dương đó.

Hôm nay, bà ngoại bị ốm và mẹ sai bé khăn đỏ mang cơm cho bà. Khi đi mẹ có dặn bé khăn đỏ không được la cà, tức là từ một ô chỉ có thể đi sang ô kề cạnh phía bên phải hoặc kề cạnh phía dưới (tất nhiên là ô đó phải không có sói).

Trên đường đi, bé khăn đỏ muốn hái tặng bà một bó hoa đẹp nhất. Em hãy tính xem bó hoa đẹp nhất mà bé khăn đỏ có thể hái được là bao nhiêu và hãy giúp bé khăn đỏ hiếu thảo tìm một đường đi để hái được bó hoa như vậy nhé (Ở đây ta quy ước “độ đẹp” của bó hoa là tổng “độ đẹp” của tất cả các bông hoa của bó hoa đó).

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương M , N cách nhau bởi một khoảng trắng;
• M dòng tiếp theo, dòng thứ i chứa N số nguyên aij là thông tin về các ô trên hàng thứ i .

Dữ liệu ra:

• Ghi ra một dòng duy nhất là “độ đẹp” của bó hoa đẹp nhất hái được (nếu không thể đến được nhà bà thì ghi ra số -1 ) ;

Ví dụ:

Dữ liệu vào:

4 5
0 3 0 0 0
1 -1 2 5 0
1 2 -1 -1 0
-1 1 1 1 0

Dữ liệu ra:

10

Giải thích:

• Những ô tô màu vàng là hành trình đi (trừ ô đầu và ô cuối)

Giới hạn:

2 <= M, N <= 1000
-1 <= aij <= 1000

Bài này e chỉ làm đc có 50% số test thôi.

#include <bits/stdc++.h>

using namespace std;

int m, n, tong = 0;
int f[1005][1005];

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> f[i][j];
        }
    }
    int i = 1, j = 1, a, b;
    while(i != m || j != n){
        if(i < m){
            a = f[i+1][j];
        } else {
            a = -1;
        }
        if(j < n){
            b = f[i][j+1];
        } else {
            b = -1;
        }
        if(max(a, b) != -1){
            if(max(a,b) == a){
                i++;
            } else {
                j++;
            }
        } else {
            cout << -1;
            return 0;
        }
        tong += f[i][j];
    }
    cout << tong;
    return 0;
}

[HR16 (Gà Coder)]

Đăng code lên thì dùng markdown nha bạn.

Cách post Code dùng Markdown trong Category Programming

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null statement" to t…

---

Cách làm của bạn là đi theo ô lớn nhất, cách này sẽ sai nếu đường đi để được bó hoa đẹp nhất hơi vòng vèo. Xét thử trường hợp sau:

	1	2	3
1	0	2	5
2	1	0	6
3	-1	100	0

Đường đi của bé quàng khăn đỏ theo đoạn code của bạn sẽ là

• (1;1) (0) -> (1;2) (vì 2 > 1) -> (1;3) (vì 5 > 0) -> (2;3) (6) -> (3;3) (0)
• Cộng lại được 0 + 2 + 5 + 6 + 0 = 13

Trong khi đường đi đúng là:

• (1;1) (0) -> (1;2) (2) -> (2;2) (0) -> (3;2) (100)
• Cộng lại được 0 + 2 + 0 + 100 = 102

Bài này phải tính hết toàn bộ đường đi có thể có.

[kisuluoibieng (Tên Gì Cũng Được)]

này là code theo kiểu nhìn hướng nào được cao điểm thì đi vô thôi, không cần biết các step sau đây mà
bài này quy hoạch động, duyệt mảng theo từng đường chéo phụ là xong, mỗi ô chỉ có thể được đi từ ô bên trái, hoặc ô bên trên mà thôi, công thức truy hồi cũng chỉ có câu if
trong hơn 2 tiếng đồng hồ, có 2 account đăng kí mới, cùng post đề bài từ vnoi :))

[tntxtnt]

đi qua trái lên trên được ko nhỉ :V
ví dụ

0 3 4
1 2 0

đi 0+1+2+3+4+0 thay vì 0+3+4+0

à có giới hạn

Khi đi mẹ có dặn bé khăn đỏ không được la cà, tức là từ một ô chỉ có thể đi sang ô kề cạnh phía bên phải hoặc kề cạnh phía dưới (tất nhiên là ô đó phải không có sói).

[nitro2 (Nhím)]

@tntxtnt

đi qua trái lên trên được ko nhỉ :V

@linhmoi

không được la cà, tức là từ một ô chỉ có thể đi sang ô kề cạnh phía bên phải hoặc kề cạnh phía dưới

Bài này áp dụng Dijkstra’s algorithm ngược (tìm đường đi dài nhất) chắc được.

[linhmoi (lính mới)]

E tính hết toàn bộ đường đi có thể có r những mà bị time limit và một vài test còn sai, e debug mãi mà ko sửa đc

#include <bits/stdc++.h>

using namespace std;

int m, n, tong = 0, tong1 = 0;
int f[1005][1005];
vector<int> ip;
vector<int> jp;
vector<int> sht;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> f[i][j];
        }
    }
    int i = 1, j = 1, a, b;
    for(int g = 0; g <= ip.size(); g++){
        while(i != m || j != n){
            if(i < m){
                a = f[i+1][j];
            } else {
                a = -1;
            }
            if(j < n){
                b = f[i][j+1];
            } else {
                b = -1;
            }
            if(a != -1 && b != -1){
                if(min(a,b) == a){
                    ip.push_back(i+1);
                    jp.push_back(j);
                } else {
                    ip.push_back(i);
                    jp.push_back(j+1);
                }
                sht.push_back(tong);
            }
            if(max(a, b) != -1){
                if(max(a,b) == a){
                    i++;
                } else {
                    j++;
                }
            } else {
                i = m; j = m;
            }
            tong += f[i][j];
        }
        if(tong > tong1)
            tong1 = tong;
        if(g <= ip.size()){
            tong = sht[g];
            i = ip[g];
            j = jp[g];
        }
    }
    cout << tong1;
    return 0;
}

[HR16 (Gà Coder)]

Mới nghĩ ra cách này, test sương sương thì có vẻ đúng.

Cho mảng dp có kích thước MxN, duyệt bằng i,j.

Nếu i = 1, j = 1 thì dp[i][j] = (1,1)
Nếu (i,j) >= 0:

• Nếu i = 1, j > 1:
  • Nếu dp[i][j - 1] >= 0 thì dp[i][j] = (i,j) + dp[i][j - 1] (lấy ô cùng vị trí cộng cái bên trái)
  • Ngược lại thì dp[i][j] = -1
• Nếu i > 1, j = 1:
  • Nếu dp[i - 1][j] >= 0 thì dp[i][j] = (i,j) + dp[i - 1][j] (lấy ô cùng vị trí cộng cái bên trên)
  • Ngược lại thì dp[i][j] = -1
• Nếu i > 1, j > 1 thì dp[i][j] = (i,j) + max(dp[i - 1][j], dp[j - 1][i])

Nếu (i,j) = -1 thì dp[i][j] = -1

P/s: Giờ mới để ý là bài này đã gợi ý dùng QHĐ ngay từ đầu rồi. Tên bài là DPFLOWER, DP là viết tắt của Dynamic Programming tức Quy Hoạch Động.