# DYNAMIC PROGRAMING

## 1. Mua sắm

> ###### Tags: DP, Greedy.
> https://codeforces.com/gym/508163/problem/F

### Subtask 1 : $n = 1$

Với $n = 1$ thì đáp án của ta là : $min(\lfloor\frac{k}{c_1}\rfloor, l_1)\times e_1$.

### Subtask 2, 3 : $n \le 100, l_i \le 10$.

Quy hoạch động Knapsack cơ bản :
* Với $f[i][j]$ là giá trị dinh dưỡng lớn nhất của một cách chọn khi đã xét đến loại thực phẩm thứ $i$ và đã tốn số tiền là $j$.

* Hoặc với công thức $f[j]$ là giá trị dinh dưỡng lớn nhất của một cách chọn khi đã tốn số tiền là $j$.

### Subtask 6 : $n \le 10^5, l_i \le 10^9$.

Ta gọi $vec[i]$ $(1 \le i \le k)$ là tập hợp giá trị dinh dưỡng các thực phẩm có giá bán là $i$.

**Ví dụ** :
* Ta có các loại thực phẩm $(c_i, e_i, l_i) : (2, 5, 3), (2, 4, 4)$
* Thì $vec[2]$ của ta là : ${4, 4, 4, 4, 5, 5, 5}$.

**Nhận xét** : trong tập $vec[i]$ các thực phẩm đều có giá bán là $i$ nên ta ưu tiên các thực phẩm có giá trị ưu tiên từ cao đến thấp. Cụ thể là với mỗi tập $vec[i]$ ta chỉ chọn được số lượng thực phẩm tối đa là : $min(\lfloor\frac{k}{i}\rfloor, vec.size())$.

Sau đó ta quay lại bài toán Knapsack cơ bản.

**Code** : https://ideone.com/Ak3aZj.

## 2. Nông trại.

> ###### Tags: DP, Greedy.
> https://codeforces.com/group/hlS1ctLR9t/contest/508163/problem/I

### Subtask 1 : $n, Q, P_i \le 100$

Gọi $f[i][j]$ là giá trị lớn nhất khi xét đến ngày thứ $i$ và đã gieo $j$ hạt giống.

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }

int f[1005][1005], n, k, q, a[1005], p[1005];
 
void solve() {
	cin >> n >> k >> q;
	
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	for (int i = 1; i <= n; i++) cin >> p[i];
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= p[i]; j++) f[i][j] = j * a[i];	
		for (int j = 0; j <= q; j++) maximize(f[i][j], f[i - 1][j]);
		
		if (i >= k) {
			for (int j = 1; j <= p[i]; j++)
				for (int x = j; x <= q; x++) maximize(f[i][x], f[i - k][x - j] + j * a[i]);
		}
	}
	
	int res = 0;
	for (int i = 0; i <= q; i++) maximize(res, f[n][i]);
	
	cout << res;
}

Độ phức tạp : $O (n \times P \times Q)$.

### Subtask 2 : $n, Q, P_i \le 1000$

* Nhận xét : Khi xét đến ngày trồng thứ i thì :

> Trạng thái $f[i][x]$ $(1 \le x \le q)$ phải được cập nhật từ trạng thái $f[i - k][y]$ $(y \le x)$ trước đó mà $x - y \le P_i$ : Vì số hạt giống tối đa có thể trồng ở ngày $i$ là $P_i$.

> Trạng thái $f[i][x + 1]$ sẽ được cập nhật từ trạng thái $f[i - k][y]$ mà $x + 1 - y \le P_i$.

> Tương tự .....

Ta duy trì một sẽ $std::multiset$

if (i >= k) {
	multiset<int> s;

	for (int x = 1; x <= q; x++) {
		s.insert(f[i - k][x - 1] - (x - 1) * a[i]);

		if (x - p[i] - 1 >= 0) {
			auto it = s.lower_bound(f[i - k][x - p[i] - 1] - (x - p[i] - 1) * a[i]);
			s.erase(it);
		}

		auto mx = s.end();
		--mx;

		maximize(f[i][x], *(mx) + x * a[i]);
	}	
}

Độ phức tạp : $O (n \times Q \times log2(Q))$.

### Subtask 4 : $n, Q, P_i \le 10000$

Tương tự nhận xét từ subtask $2$ nhưng thay vì dùng $std::multiset$ thì ta sẽ dùng $deque$ (hàng đợi hai đầu) để làm công việc tương tự.

if (i >= k) {
	deque<int> pq; 
 
	for (int x = 1; x <= q; x++) {
		while (pq.size() && f[i - k][x - 1] - (x - 1) * a[i] >= f[i - k][pq.back()] - (pq.back()) * a[i]) 
		pq.pop_back();
		pq.push_back(x - 1);
 
		while (pq.front() <= x - p[i] - 1) pq.pop_front(); 
 
		maximize(f[i][x], f[i - k][pq.front()] - pq.front() * a[i] + x * a[i]);
	}	
}

Độ phức tạp : $O (n \times Q)$

### Subtask 3 : $P_1 = P_2 =... = P_n$

* Nhận xét : Với việc $P_i$ bằng nhau, ta thấy rằng để tối đa giá trị cần tìm, thì tập các ngày cần trồng hạt giống thường cố gắng trồng đủ $P$ hạt, trừ khi sau khi trồng xong thì vẫn còn dư hạt.

* Gọi $f[i][j]$ là giá trị lớn nhất khi xét đến ngày thứ $i$ và đã gieo $j$ hạt giống.

* Nhưng bây giờ với mỗi ngày $i$ ta chỉ có những trạng thái như sau :

> Không trồng hạt nào.

> Gieo trồng đúng $P$ hạt.

> Hoặc gieo trồng $Q % P$ hạt.

**Code** : https://ideone.com/zC6Z0p.

## 3. Đóng gói.
> #### Tags: DP, Greedy.
> https://codeforces.com/group/hlS1ctLR9t/contest/508163/problem/H

### Subtask 1 : $L \le 10^9, N \le 20$

* Với $N \le 20$ ta có thể sinh dãy nhị phân độ dài $n$. Mỗi dãy nhị phân được sinh ra, ta thêm lần lượt các món hàng vào thùng, với phần tử $0$ được xếp vào thùng $1$, phần từ $1$ được xếp vào thùng $2$ hoặc có thể ngược lại.

* Độ phức tạp : $O (2^N \times N)$.

### Subtask 2 : $1 \le a_i \le 2; L = 100; N \le 10^6$

* Gọi $sum = a_1 + a_2 + ... + a_n$
* Đáp án sẽ là : $\lfloor (\frac{sum}{L}) \rfloor$ + $sum$ mod $L$ $ > 0$
* Độ phức tạp : $O(N)$

### Subtask 3 : $L \le 30; N \le 10^4$

* Đặt mảng quy hoạch động : $f[i][x][y]$ là số thùng ít nhất dùng để khi xét đến món hàng thứ $i$ và hiện tại lúc đó thúng $1$ đã chứa $x$ đơn vị cân nặng, thùng $2$ chứa $y$ đơn vị cân nặng.

void sub3() {
	memset(f, 0x3f, sizeof (f));
	f[0][0][0] = 2;
	
	for (int i = 1; i <= n; i++)
		for (int l1 = 0; l1 <= lim; l1++)
			for (int l2 = 0; l2 <= lim; l2++) {
				if (a[i] + l1 <= lim) minimize(f[i][a[i] + l1][l2], f[i - 1][l1][l2]);
				if (a[i] + l2 <= lim) minimize(f[i][l1][a[i] + l2], f[i - 1][l1][l2]);
				minimize(f[i][a[i]][l2], f[i - 1][l1][l2] + 1);
				minimize(f[i][l1][a[i]], f[i - 1][l1][l2] + 1);
			}	
	
	for (int l1 = 0; l1 <= lim; l1++) for (int l2 = 0; l2 <= lim; l2++) minimize(res, f[n][l1][l2]);
	cout << res << '\n';
}

### Subtask 4 : $L \le 5000; N \le 100$

* Nhận xét : Với $N \le 100$ thì số thùng cần dùng của ta cũng chỉ tối đa $100$ mà thôi!
* Nên ta có thể đặt mảng quy hoạch động là : $f[i][cnt][x]$ trả về $y$ nhỏ nhất sao cho tồn tại $1$ cách xếp $i$ món hàng đầu tiên vào đúng $cnt$ thùng, trong đó hiện tại thùng $1, 2$ đang chứa lần lượt là $x, y$.

Giả sử đang ở trạng thái $f[i - 1][cnt][x]$ thì công thức quy hoạch động của ta của ta là :

* Nếu có thể thêm món hàng $i$ vào thùng $1$ (nếu có thể) thì : $f[i][cnt][x + a[i]] = f[i - 1][cnt][x]$

* Nếu có thể thêm món hàng $i$ vào thùng $2$ (nếu có thể) thì : $f[i][cnt][x] = f[i - 1][cnt][x] + a[i]$

* Thay thùng 1 bằng một thùng mới : $f[i][cnt + 1][a[i]] = f[i - 1][cnt][x]$.

* Thay thùng 2 bằng một thừng mơi : $f[i][cnt + 1][x] = a[i]$

### Subtask 5 : $L \le 5000; N \le 10^4$

* Thay đổi từ subtask 4, ta đặt mảng quy hoạch động : **pair<int, int>** $f[i][x] = (cnt, y)$ khi xét tới món hàng thứ $i$ và thùng thứ $1$ chứa $x$ thì thùng thứ $y$ và số thùng ít nhất là $cnt$.

void sub45() {
	for (int i = 0; i <= n; i++) for (int j = 0; j <= lim; j++) f[i][j] = {INF, 0};
	f[0][0] = {2, 0}; // Chu y so thung duoc su dung luon luon >= 2
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= lim; j++) {
			
            if (j + a[i] <= lim) f[i][j + a[i]] = min(f[i][j + a[i]], f[i - 1][j]); 
            // Them mon hang thu i vao thung thu 1 neu co the
			
            
            f[i][a[i]] = min(f[i][a[i]], make_pair(f[i - 1][j].first + 1, f[i - 1][j].second));
            // Dong thung 1 va mo mot thung moi thay the thung 1
			
            if (f[i - 1][j].second + a[i] <= lim) f[i][j] = min(f[i][j], make_pair(f[i - 1][j].first, f[i - 1][j].second + a[i]));
             // Them mon hang thu i vao thung thu 2 neu co the
			
            f[i][j] = min(f[i][j], make_pair(f[i - 1][j].first + 1, a[i]));
            
            // Dong thung 2 va mo mot thung moi thay the thung 2
			
            if (i == n) minimize(res, f[n][j].first);
		}
	}
	cout << res;
}

**Code** : https://ideone.com/WHD3JT

## 4. Kho báu.
> #### Tags: DP, bitset.
> https://codeforces.com/group/hlS1ctLR9t/contest/508163/problem/G

### Subtask 1 : $n \le 10$

Ta gọi hàm đệ quy : $back(l, x)$ có nghĩa là đã xét đến rương thứ $i$ và đã mở được đến rương thứ $x$.

int back(int l, int x) {
	if (l > x || l > n) return 0;
	int res = 0;
	
	maximize(res, a[l] + back(l + 1, x));
	maximize(res, back(l + 1, min(n, x + a[l])));
	
	return res;
}

### Subtask 2 : $n \le 1000$.

* Ta gọi hàm quy hoạch động $f[i][x]$ là số tiền lớn nhất thu được khi đang xét đến rương thứ $i$ và đã mở được đến rương thứ $x$.

int back(int l, int x) {
	if (l > x || l > n) return 0;
	int &res = f[l][x];
	if (res != -1) return res;
	res = 0;
	
	maximize(res, a[l] + back(l + 1, x));
	maximize(res, back(l + 1, min(n, x + a[l])));
	
	return res;
}
 
void solve() {
	memset(f, -1, sizeof (f));
	cout << back(1, 1);
}

### Subtask3 : $n \le 10 ^ 5$.

* Nhận xét : Để mở được rương thứ $i$ ta cần chọn ra một tập hợp các rương có chỉ số $j < i$ sao cho tổng các rương này lớn hơn hoặc bằng $i - 1$. Để khi xét đến rương thứ $i$ được kết quả tối ưu, ta sẽ tìm ra một tập rương như đã nói mà có tổng $sum$ nhỏ nhất lớn hơn hoặc bằng $i - 1$, thì kết quả của ta thu được tại $i$ là $a_1 + a_2 + .. + a_i - sum$.

* Ta có thể dùng Knapsack thông thường để tính các giá trị $sum$ có tồn tại hay không ?. Nhưng bằng cách này sẽ không thể AC khi $n \le 10^5$. Thay vào để ta có thể tính Knapsack bằng việc dùng $std::bitset$

* Với mỗi bit thứ $i$ trên bitset đại dương cho giá trị $sum = i$ đó có tồn tại hay không ?

* Ví dụ trong ta đang tồn tại các $sum = (0, 1, 3, 5)$. Thì bitset của ta sẽ là $000101011$ (được đánh số từ phải sang trái, 0, 1, 2.... ). Nếu ta thêm một phần tử $x = 3$ thì rõ ràng tập $sum = (3, 4, 6, 8)$, bitset của ta là $00101011000$

* Cách thêm **bitset |= bitset << (x)**

    bitset<MAXN * 2> g;
	void solve() {
		g[a[1]] = true;
		
		int res = a[1], j = 1;
        // biến j đến duy trì sum = j nhỏ nhất thỏa mãn.
		int sum = a[1];
		g[0] = false;
		
		for (int i = 2; i <= n; i++)  {
			sum[i] += a[i];
			
			g |= (g << (a[i])); // update tập thỏa mãn
				
			maximize(j, i - 1);
			while (!g[j] && j < n * 2) ++j; // tìm sum = j nhỏ nhất thỏa mãn g[j] = 1.
            // để không bị tràn giá trị của sum khi ta dịch bit nên ta sẽ cho sum thỏa trong khoảng <= 2 * n.
			
			if (!g[j]) break;
            // nếu không sum = j không tồn tại, thì những sum > j sẽ không tồn tại
            
			maximize(res, sum[i] - j); // cập nhật kết quả.
			
			g[i - 1] = false;// vì như đã nói khi xét đến rương i thì cần phải mở i - 1 rương
            // nên khi xét đến rương i ta đều phải bỏ đi tất cả các sum < i - 1.
		}
		cout << res << '\n';
	}

**Code :** https://ideone.com/JhQ24r.