***Định nghĩa trạng thái DP:***
- $dp[i][j][0]$ là tổng lớn nhất khi xét đến phần tử thứ $i$, đã thực hiện tối đa $j$ lần xóa và không thực hiện xóa ở vị trí hiện tại.
- $dp[i][j][1]$ là tổng lớn nhất khi xét đến phần tử thứ $i$, đã thực hiện tối đa $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:
$$
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:
$$
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ả $dp[n][j][0]$ và $dp[n][j][1]$ với j thuộc $[0, k]$.
***Độ phức tạp và bộ nhớ:***
- Số trạng thái cần tính: $O(n×k)$
- Thời gian tính một trạng thái: $O(1)$
- Độ phức tạp tổng: $O(n×k)$
- Bộ nhớ: $O(n×k×2)$
- **Vì $n,k ≤ 5000$ nên sẽ không đủ bộ nhớ để lưu mảng $dp[n][k][2]$**
***Tối ưu bộ nhớ***
- Vì chúng ta chỉ sử dụng 2 trạng thái $i$ và $i-1$ nên ta chỉ cần lưu 2 trạng thái đó
- Mảng dp mới sẽ là: $dp[2][k][2]$
- Bộ nhớ sau tối ưu: $O(2×k×2)$
***Code mẫu:***
```
// 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;
}
```
nhanzzzz
Created at
4 likes