Solutions of Delete operation

Select solution language

nhanzzzz Created at 5 likes

***Định nghĩa trạng thái DP:*** -

d p [i] [j] [0]

$dp[i][j][0]$ là tổng lớn nhất khi xét đến phần tử thứ

i

$i$ , đã thực hiện tối đa

j

$j$ lần xóa và không thực hiện xóa ở vị trí hiện tại. -

d p [i] [j] [1]

$dp[i][j][1]$ là tổng lớn nhất khi xét đến phần tử thứ

i

$i$ , đã thực hiện tối đa

j

$j$ lần xóa và có thể đang thực hiện một lần xóa. ***Công thức chuyển trạng thái:*** - Khi không xóa phần tử i:

d p [i] [j] [0] = m a x (d p [i - 1] [j] [0] + A [i], d p [i - 1] [j] [1] + A [i])

$dp[i][j][0] = max(dp[i-1][j][0] + A[i], dp[i-1][j][1] + A[i])$ (Có thể đến đây từ trạng thái trước đó mà không xóa gì, hoặc từ trạng thái đang xóa trước đó). - Khi bắt đầu hoặc đang thực hiện một lần xóa:

d p [i] [j] [1] = m a x (d p [i - 1] [j - 1] [0], d p [i - 1] [j] [1])

$dp[i][j][1] = max(dp[i-1][j-1][0], dp[i-1][j][1])$ (Có thể bắt đầu một lần xóa mới từ trạng thái trước đó hoặc tiếp tục xóa từ trạng thái đã xóa trước đó). ***Đáp án cuối cùng:*** - Kết quả là giá trị lớn nhất trong tất cả

d p [n] [j] [0]

$dp[n][j][0]$ và

d p [n] [j] [1]

$dp[n][j][1]$ với j thuộc

[0, k]

$[0, k]$ . ***Độ phức tạp và bộ nhớ:*** - Số trạng thái cần tính:

O (n \times k)

$O(n×k)$ - Thời gian tính một trạng thái:

O (1)

$O(1)$ - Độ phức tạp tổng:

O (n \times k)

$O(n×k)$ - Bộ nhớ:

O (n \times k \times 2)

$O(n×k×2)$ - **Vì

n, k \leq 5000

$n,k ≤ 5000$ nên sẽ không đủ bộ nhớ để lưu mảng

d p [n] [k] [2]

$dp[n][k][2]$ ** ***Tối ưu bộ nhớ*** - Vì chúng ta chỉ sử dụng 2 trạng thái

i

$i$ và

i - 1

$i-1$ nên ta chỉ cần lưu 2 trạng thái đó - Mảng dp mới sẽ là:

d p [2] [k] [2]

$dp[2][k][2]$ - Bộ nhớ sau tối ưu:

O (2 \times k \times 2)

$O(2×k×2)$ ***Code mẫu:***

/ n h a n z z z z - T H P T X u a n L o c # \in c l u d e < b i t \frac{s}{s} t d c + + . h > # d e f \in e \int l o n g l o n g # d e f \in e e n d l \n # d e f \in e t a s k main u \sin g n a m e s p a c e s t d; / c o n s t \int max n = 5005; \int n, k, a r r [max n], d p [2] [max n] [2]; s i g \neq d m a \in () {i o s : : s y n c_{w} i t h_{s} t d i o (0); c \in . t i e (0); c o u t . t i e (0); if (f o p e n (t a s k .inp, r)) {e o p e n (t a s k .inp, r, s t d \in); e o p e n (t a s k .out, w, s t d o u t);} / c \in 〉 n 〉 k; f or (\int i = 1; i \leq n; i + +) {c \in 〉 a r r [i];} / d p [0] [0] [0] = d p [0] [0] [1] = 0; f or (\int i = 1; i \leq n; i + +) {if (i & 1) {d p [1] [0] [0] = d p [0] [0] [0] + a r r [i]; d p [1] [0] [1] = d p [0] [0] [1] + a r r [i]; f or (\int j = 1; j \leq k; j + +) {d p [1] [j] [0] = max (d p [0] [j] [0] + a r r [i], d p [0] [j] [1] + a r r [i]); d p [1] [j] [1] = max (d p [0] [j - 1] [0], d p [0] [j] [1]);}} e l s e {d p [0] [0] [0] = d p [1] [0] [0] + a r r [i]; d p [0] [0] [1] = d p [1] [0] [1] + a r r [i]; f or (\int j = 1; j \leq k; j + +) {d p [0] [j] [0] = max (d p [1] [j] [0] + a r r [i], d p [1] [j] [1] + a r r [i]); d p [0] [j] [1] = max (d p [1] [j - 1] [0], d p [1] [j] [1]);}}} \int o u t = - 9 e 18; f or (\int j = 0; j \leq k; j + +) {o u t = max ({o u t, d p [n % 2] [j] [1], d p [n % 2] [j] [0]});} c o u t 〈 o u t;}

$// nhanzzzz - THPT Xuan Loc #include <bits/stdc++.h> #define int long long #define endl "\n" #define task "main" using namespace std; // const int maxn = 5005; int n, k, arr[maxn], dp[2][maxn][2]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } // cin >> n >> k; for(int i=1;i<=n;i++){ cin >> arr[i]; } // dp[0][0][0] = dp[0][0][1] = 0; for(int i=1;i<=n;i++){ if(i & 1){ dp[1][0][0] = dp[0][0][0] + arr[i]; dp[1][0][1] = dp[0][0][1] + arr[i]; for(int j=1;j<=k;j++){ dp[1][j][0] = max(dp[0][j][0] + arr[i], dp[0][j][1] + arr[i]); dp[1][j][1] = max(dp[0][j-1][0], dp[0][j][1]); } }else{ dp[0][0][0] = dp[1][0][0] + arr[i]; dp[0][0][1] = dp[1][0][1] + arr[i]; for(int j=1;j<=k;j++){ dp[0][j][0] = max(dp[1][j][0] + arr[i], dp[1][j][1] + arr[i]); dp[0][j][1] = max(dp[1][j-1][0], dp[1][j][1]); } } } int out = -9e18; for(int j=0;j<=k;j++){ out = max({out, dp[n%2][j][1], dp[n%2][j][0]}); } cout << out; }$