Có khoảng tối đa $\sqrt{2 * T}$ các giá trị $w$ khác nhau trong mảng, vậy ta có thể đếm số lần một giá trị $w$ xuất hiện.
Gọi $c_i$ là số lần giá trị $w_i$ xuất hiện với $i \in [1, T]$
Khi này bài toán sẽ trở thành bài toán knapsack cổ điển như sau: cho các cặp giá trị $w_i$ và $c_i$, hỏi ta có thể tạo ra $x$ từ các cặp số này hay không? Biết rằng mỗi $w_i$ được sử dụng tối đa $c_i$ lần.
Nó sẽ gần giống với bài này: https://marisaoj.com/problem/156
Với mỗi giá trị $i$, ta chia nhỏ $c_i$ thành tổng của $2^x$ sao cho cộng lại bằng đúng $c_i$, với mỗi giá trị $2^x$, ta sẽ có thể tạo thành giá trị $w_i * 2^x$. Độ phức tạp sẽ là $\mathcal{O}(T\sqrt{2 * T})$
Do chúng ta chỉ cần kiểm tra xem việc tạo thành $i$ là thực hiện được hay không, ta có thể dùng bitset để thực hiện các thao tác tính toán một cách nhanh hơn, giảm được độ phức tạp xuống $\mathcal{O}(\frac{T\sqrt{2 * T}}{32})$
Code tham khảo:
```cpp
#include "bits/stdc++.h"
using namespace std;
bitset<(int)1e6 + 1> dp;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, T;
cin >> n >> T;
vector<int> w(n);
for (int i = 0; i < n; i++) {
cin >> w[i];
}
sort(w.begin(), w.end());
dp[0] = 1;
for (int i = 0; i < n;) {
int nxt = upper_bound(w.begin(), w.end(), w[i]) - w.begin();
int c = nxt - i;
for (int k = 1; c > 0; k <<= 1) {
int x = min(k, c);
c -= x;
dp |= dp << (w[i] * x);
}
i = nxt;
}
for (int i = 1; i <= T; i++) {
cout << dp[i];
}
}
```
bean
Created at
2 likes