## Cách tiếp cận ngây thơ
- Ta nghĩ ngay đến cách gọi `dp[i][j]` là mảng quy hoạch động xét xem có thể tạo được tổng $j$ thông qua sử dụng các phần tử từ $1$ đến $i$
- Tuy nhiên, Nếu mảng chỉ trả về `true/false` thì ta không thể quản lý được xem tổng IQ và EQ riêng biệt có thoả mãn điều kiện đề bài không.
- Vì thế, ta lại nghĩ tiếp rằng nếu vậy thì `dp[i][j]` sẽ trả về IQ hoặc EQ lớn nhất có thể. Nếu giá trị của nó nằm trong đoạn $[0, j]$ thì thoả
- Vậy thì độ phức tạp của thuật toán sẽ là $O(n \times H)$ với $H$ là số lượng giá trị tổng có thể xảy ra.
- Do có thể có $2 \times 500 \times 1000$ giá trị nên cách này rõ ràng **không hiệu quả**
## Cách giải tối ưu hơn
- Ta gọi $dp[i][j]$ là giá trị EQ lớn nhất có thể xảy ra trong số tập có tổng IQ bằng $j$ và chỉ gồm các con bò trong khoảng $[1, i]$
- Ta giải quyết như một bài dp knapsack bình thường. Chỉ có điều, $i$ có thể âm nên ta sẽ tịnh tiến nhãn.
- Nghiệm của bài toán sẽ là $\max^{maxS}_{s=-maxS} s + dp[n][s + \text{OFFSET}]$ với `OFFSET` là giá trị mà ta dùng để tịnh tiến nhãn
- Độ phức tạp của thuật toán sẽ là $O(n^2 \times maxS)$ với `maxS` là $\max$ của giá trị lớn nhất và trị tuyệt đối của giá trị nhỏ nhất
Nhìn độ phức tạp các bạn sẽ hơi rén do số lượng phép tính có thể lên đến $5 \times 10^8$
Nhưng không sao, chỉ cần code khéo tí là qua do những bài QHĐ hằng số thường khá bé :))))
### Code tham khảo
```cpp
#include <bits/stdc++.h>
#define taskname "main"
#define debug(a, l, r) for (int _i = l; _i <= r; _i++) cout<<(a)[_i]<<' '; cout<<'\n'
#define debug_m(a, li, lj, ri, rj) for (int _i = li; _i <= ri; _i++){for (int _j = lj; _j <= rj; _j++) cout<<(a)[_i][_j]<<' '; cout<<'\n';} cout<<'\n'
using namespace std;
const int
maxN = 500,
maxS = 5e5,
maxS2 = maxS<<1;
int n,
a[maxN + 1],
b[maxN + 1],
dp[maxS2 + 1][2];
void move(){
for (int i = 0; i <= maxS2; i++){
dp[i][0] = max(dp[i][0], dp[i][1]);
dp[i][1] = INT_MIN;
}
}
void init(){
cin>>n;
for (int i = 1; i <= n; ++i)
cin>>a[i]>>b[i];
for (int i = 0; i <= maxS2; i++)
dp[i][0] = dp[i][1] = INT_MIN;
dp[maxS][0] = 0;
}
void solve(){
for (int i = 1; i <= n; i++){
for (int tmp_s = maxS; tmp_s >= -maxS; tmp_s--){
if (-maxS <= tmp_s - a[i] && tmp_s - a[i] <= maxS){
int lbl = tmp_s + maxS;
if (dp[lbl - a[i]][0] != INT_MIN)
dp[lbl][1] = max(dp[lbl][1], dp[lbl - a[i]][0] + b[i]);
}
}
move();
}
int res = 0;
for (int tmp_s = 0; tmp_s <= maxS; tmp_s++){
int lbl = tmp_s + maxS;
if (dp[lbl][0] >= 0)
res = max(res, tmp_s + dp[lbl][0]);
}
cout<<res;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
#endif
init(); solve();
}
```
minhpnk2
Created at
0 likes