VOI 06 Bài 1 - Chọn ô

Xem dạng PDF
Gửi bài giải
Điểm: 0,12 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Vietnam Olympiad of Informatics 2006 - Bảng B
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bảng hình chữ nhật kích thước ~4×n~ ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô ~(i,j)~. Trên mỗi ô ~(i,j)~ có ghi một số nguyên ~a_{i,j}~, ~i = 1, 2, 3, 4;~ ~j = 1, 2, \dots, n~. Một cách chọn ô là việc xác định một tập con khác rỗng ~S~ của tập tất cả các ô của bảng sao cho không có hai ô nào trong ~S~ có chung cạnh. Các ô trong tập ~S~ được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. Tìm cách chọn sao cho trọng lượng là lớn nhất.

Ví dụ: Xét bảng với ~n = 3~ trong hình vẽ dưới đây:

image

Cách chọn cần tìm là tập các ô ~S = \{(3,1), (1,2), (4,2), (3,3)\}~ với trọng lượng 32.

Input

Dòng đầu tiên chứa số nguyên dương n là số cột của bảng.

Cột thứ j trong số n cột tiếp theo chứa 4 số nguyên ~a_{1,j}~ , ~a_{2j,}~ , ~a_{3,j}~ , ~a_{4,j}~, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng.

Output

Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.

Giới hạn

Trong tất cả các test: ~n \leq 10\,000~, ~|a_{i,j}| \leq 30\,000~.

Có 50% số lượng test với ~n \leq 1000~.

Sample Input

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

Sample Output

32

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    ngoannam123456789  đã bình luận lúc 21, Tháng 12, 2025, 16:01

    Hint

    dp 5 chiều cho những trường hợp mà các cạnh không kề.

    Solve

    Tạo 1 mảng 5 chiều dp[hang][a1][a2][a3][a4] (a, a2, a3, a4 là trạng thái của cột = 0 nếu không nhận, = 1 nếu nhận ).

    Xếp lại Input theo a[hang][cot] ( cot <= 4 ).

    dp[i][a1][a2][a3][a4] là giá trị lớn nhất nếu lấy giá trị ở [a1][a2][a3][a4] tại hàng i

    Nhứng trạng thái bao gồm 0000, 1000, 0100, 0010, 0001, 1010, 1001, 0101.

    d[i][0][0][0][1] = max
    ({
    y[i][4],
    y[i][4] + d[i-1][1][0][0][0],
    y[i][4] + d[i-1][0][1][0][0],
    y[i][4] + d[i-1][0][0][1][0],
    y[i][4] + d[i-1][1][0][1][0],
    y[i][4] + d[i-1][0][0][0][0]
    }); ....tt

    Chú ý nếu không chọn là max thì ans = max của a[i][j].

    Cho ai muốn kiểm tra kq

    demo


  • 1
    vominhmanh10  đã bình luận lúc 17, Tháng 11, 2025, 14:24 ← sửa 10

    mọi người xem code này sai chỗ nào mà test 15 debug không ra
    thì mik qhđ các trạng thái là cột i và tập chọn mask => dp[i][mask] mã bị ngược thành dp[mask][i]
    để nhanh nên gom các mask hợp lệ của 1 cột để duyệt nhanh, tính mảng cộng dồn cho mỗi cột mỗi mask
    kiểm tra 2 cột(mask i, j) ko trùng hàng bằng i & j == 0 

    import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(4)]
    mask = [0, 1, 2, 4, 5, 8, 9, 10]
    pre = [[0] * n for _ in range(11)]

    for i in range(n):
        for j in mask:
            for k in range(4):
                if (j >> k) & 1: pre[j][i] += a[k][i]
    dp = [[-10**18] * n for _ in range(11)]
    for j in mask:
        dp[j][0] = pre[j][0]
    for i in range(1, n):
        for j in mask:
            for k in mask:
                if not (j & k): dp[j][i] = max(dp[j][i], dp[k][i - 1] + pre[j][i])
    res = -10**18
    for j in mask:
        res = max(dp[j][n - 1], res)
    print(res)
solve()

  • -1
    haiduong151109  đã bình luận lúc 22, Tháng 6, 2025, 10:41

    https://ideone.com/nm23so code e sai đâu v ạ ?


    • 1
      truonghovuviet  đã bình luận lúc 15, Tháng 7, 2025, 7:38

      Phải chọn ít nhất 1 ô.


  • -13
    phannam310810  đã bình luận lúc 17, Tháng 6, 2025, 1:33

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -16
    phannam310810  đã bình luận lúc 10, Tháng 5, 2025, 15:30

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -2
    Thanh09  đã bình luận lúc 1, Tháng 4, 2025, 7:01 ← chỉnh sửa

    ban em comment, em xin loi moi nguoi a...


    • -10
      tiendungnguyen860  đã bình luận lúc 1, Tháng 4, 2025, 8:47

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -7
      kqhuy123  đã bình luận lúc 1, Tháng 4, 2025, 8:42

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -8
      ThanhPhong  đã bình luận lúc 1, Tháng 4, 2025, 7:10

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -9
    ThanhBC1234  đã bình luận lúc 24, Tháng 2, 2025, 7:47 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    minhtuanvp2011  đã bình luận lúc 23, Tháng 2, 2025, 15:51 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    nehuy7410  đã bình luận lúc 28, Tháng 11, 2024, 12:50

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 30
    huynhquocluatit10  đã bình luận lúc 13, Tháng 4, 2024, 8:48 ← chỉnh sửa

    gợi ý:có trường hợp full âm nha


    • -1
      minha2k25cvp  đã bình luận lúc 9, Tháng 10, 2024, 14:58

      bạn có test khong ạ, mình vãn bị sai 1 test


    • -8
      duonggiabao2008  đã bình luận lúc 13, Tháng 4, 2024, 8:52

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -90
    tonblan  đã bình luận lúc 17, Tháng 3, 2024, 18:15

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -22
      hieuhfgr  đã bình luận lúc 19, Tháng 3, 2024, 8:21

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -38
    nogo007akapkn  đã bình luận lúc 8, Tháng 11, 2023, 2:28 ← sửa 3

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.