Mọi người cho em xin thuật toán bài DPVIP

Thảo luận

DPVIP - Nhân vật vô cùng quan trọng Trong rạp chiếu phim có N ghế dành cho N vị khách. Mỗi người lần lượt vào rạp xem phim và phải ngồi vào đúng chỗ của mình (người vào thứ i phải ngồi ghế thứ i). Tuy nhiên, có một ông khách VIP vào đầu tiên và được giành lấy một ghế bất kì. Mỗi người tiếp theo khi vào rạp thì ý thức hơn nên sẽ ngồi vào đúng chỗ (nếu ghế của họ chưa có người ngồi). Nhưng nếu chỗ của họ đã bị lấy mất thì họ được quyền chọn 1 ghế khác bất kì.

Ta biết Cij là độ hài lòng của vị khách thứ i khi ngồi vào ghế thứ j.

Hãy tính giá trị lớn nhất có thể của tổng độ hài lòng của N vị khách.

Dữ liệu vào:

Dòng đầu chứa số nguyên dương N. N dòng tiếp theo, dòng thứ i chứa N số nguyên Ci1, Ci2, …, CiN. Dữ liệu ra:

Một số nguyên duy nhất là giá trị lớn nhất của tổng độ hài lòng có thể được.

Ví dụ:

Dữ liệu vào: 4 2 6 8 6 5 0 6 7 8 0 1 9 2 7 2 4

Dữ liệu ra: 24 Giải thích: Khách VIP (người thứ nhất) vào ghế số 2, người thứ 2 vào ghế số 3, người số 3 vào ghế số 1, người thứ 4 vào ghế số 4, tổng độ hài lòng là 6 + 6 + 8 + 4 = 24.

Giới hạn: 1 ≤ N ≤ 1000, | ai | ≤ 109

‎

2024-11-18 15:49:46

#include <bits/stdc++.h> using namespace std; #define ll long long #define ff ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAX_N = 1001; ll matrix[MAX_N][MAX_N]; ll dpS[MAX_N];
ll dp[MAX_N];
ll maxResult = LLONG_MIN;

int main() { ff;

int n;
cin >> n;


for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        cin >> matrix[i][j];
    }
    dpS[i] = dpS[i - 1] + matrix[i][i];
}


dp[1] = dpS[n];


for (int i = 2; i <= n; ++i) {
    dp[i] = LLONG_MIN; 
    for (int j = 1; j < i; ++j) {
        
        dp[i] = max(dp[i], dp[j] - matrix[j][1] + matrix[j][i] - matrix[i][i] + matrix[i][1]);
    }
    
    maxResult = max(maxResult, dp[i]);
}


cout << max(dpS[n], maxResult);

return 0;

}

Tổng cộng 1 trả lời