## Bài 1: [Cái túi 3](https://marisaoj.com/problem/156)
- Do vật thứ $i$ có thể được dùng tối đa $a_i$ lần, ta tạo ra $a_i$ vật thứ $i$ và làm dp knapsack như bình thường, mỗi vật chỉ được chọn tối đa một lần. Nhưng thế này thì TLE.
- Vậy làm sao để vật $i$ thành các một số các vật khác $T_i$ sao cho nếu chọn $0 < x \le a_i$ lần vật $i$, luôn có cách để tạo ra nó bằng một tập con của $T_i$. Một vật mới bằng $p$ lần vật $i$ sẽ có khối lượng $w_i \times p$ và giá trị $v_i \times p$:
+ Với $a_i=2^k-1$, ta có thể tách thành $k$ vật $2^0,2^1,...,2^{k-1}$. Luôn có cách để phân tích $x$ thành tổng các lũy thừa cơ số $2$.
+ Với $a_i=2^k-1+t$, ta tách thành $k+1$ vật $2^0,2^1,...,2^{k-1},t$. Với $0 < x \le 2^k-1$, ta phân tích như bình thường. Với $2^k - 1 < x \le a_i$, ta phân tích $x-t$ như trước đó rồi thêm vật $t$ vào.
- Phân tích mỗi vật $i$ thành $\log {a_i}$ vật như trên, làm dp knapsack như bình thường.

Code:
:::spoiler

#include <bits/stdc++.h>
using namespace std;

const int MAXW = 10005, MAXN = 1005;

int n, k, dp[MAXW];

struct jew{
    int w;
    int val;
};

vector<jew> jewel;

void split(int w, int v, int a){
    int cur = 1;
    while(cur <= a){
        jewel.push_back({w * cur, v * cur});
        a -= cur;
        cur *= 2;
    }
    if(a)
        jewel.push_back({w * a, v * a});
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        split(a, b, c);
    }  

    for(int i = 0; i < jewel.size(); i++){
       for(int j = k; j >= jewel[i].w; j--){
            dp[j] = max(dp[j], dp[j - jewel[i].w] + jewel[i].val);
        }
    }

    // for(int i = 0; i < jewel.size(); i++)
    //     cout << jewel[i].val << ' ' << jewel[i].w << endl;

    int res = 0;
    for(int i = 0; i <= k; i++){
        //cout << dp[i] << ' ';
        res = max(res, dp[i]);
    }
    cout << res;
}

:::

## Bài 2: [Đất](https://marisaoj.com/problem/367)

### **Cách dễ hơn (chậm hơn)**
- Đặt $c_i = a_i-b_i$.
- Nếu $c_i$ lớn hơn $0$, thêm $c_i$ phần tử $i$ vào mảng $A'$, ngược lại thêm $-c_i$ phần tử $i$ vào mảng $B'$. Nghĩa là mảng $A'$ là những vị trí cần thêm, còn $B'$ là cần bớt.
- Trạng thái DP $f(i,j)$ là chi phí nhỏ nhất để xử lí xong $A'[1...i]$ và $B'[1...j]$. Chuyển nhãn $f(i,j) = min$
+ $f(i-1,j-1) + |A'_i-B'_j| \times z$, tương ứng với việc chuyển $1$ đất giữa $A_{A'_i}$ và $A_{B'_j}$.
+ $f(i-1,j) + x$, thêm đất vào $A_{A'_i}$.
+ $f(i,j-1)+y$, bỏ đất khỏi $A_{B'_j}$.

Code:
:::spoiler

#include <bits/stdc++.h>
using namespace std;

#define oo 2e18
#define mod 1000000007
#define int long long
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define get(x, i) (((x) >> (i)) & 1)
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define Log2(x) 63 - __builtin_clzll(x)
#define set0(d) memset(d, 0, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define setinf(d) memset(d, inf32, sizeof d)
#define Unique(v) v.erase(unique(all(v)), v.end())
#define FILENAME "f"

const int maxn = 5005;

int n, x, y, z;
int dp[maxn][maxn];

vector<int> a, b;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> x >> y >> z;

    a.push_back(0), b.push_back(0);
    for(int i = 1; i <= n; i++){
        int u, v;
        cin >> u >> v;
        if(u > v) for(int j = 1; j <= u - v; j++) b.push_back(i);
        else if(u < v) for(int j = 1; j <= v - u; j++) a.push_back(i);
    }

    setinf(dp);

    dp[0][0] = 0 ;
    for(int i = 1; i < a.size(); i++) dp[i][0] = i * x;
    for(int i = 1; i < b.size(); i++) dp[0][i] = i * y;

    for(int i = 1; i < a.size(); i++){
        for(int j = 1; j < b.size(); j++){
            dp[i][j] = min({z * abs(a[i] - b[j]) + dp[i - 1][j - 1], dp[i - 1][j] + x, dp[i][j - 1] + y});
        }
    }

    cout << dp[a.size() - 1][b.size() - 1];
}

:::

### **Cách khó hơn**
- Có các thao tác tăng $c_i$ lên $1$ hoặc $-1$, chuyển $1$ từ $c_i$ sang $c_{i-1}$ hoặc $c_{i+1}$. Làm sao để các phần tử $c_i$ thành $0$ hết.
- Trạng thái DP: $f(i, k)$, chi phí tối thiểu khi $c_j=0$ với $j \le i$, và đang "cầm" $k$ đất.
- Để đơn giản, hãy xét trường hợp chỉ được chuyển đất từ $i$ lên $j$ với $j>i$. Ở mỗi vị trí $i$, bạn được cầm lên một số đất, và có thể dùng nó để rải xuống các vị trí $>i$. Chuyển nhãn từ $f(i, k)$ lên $f(i+1,k+t)$ với $t$ là số đất cầm thêm.
- Trường hợp còn lại là, "đặt trước" đất vào $a_i$, và ở chỗ nào đó từ $i+1$ trở đi, phải lấy đất bù vào đây. Chuyển nhãn từ $f(i,k)$ lên $f(i+1,k-t)$ với $t$ số đất đặt trước.
- Trường hợp lấy thêm hoặc giảm đất thì tăng, giảm $k$.
- Đáp án là $f(n,0)$.

Code:
:::spoiler

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define fi first
#define sc second
const ll BASE = 1e4;

ll x, y, z, n;
ll a[1001] {};
ll dp[501][30001] {};
ll sum = 0;
void inp() {
    cin >> n >> x >> y >> z;
    for (int i = 1; i <= n; i++) {
        ll u, v;
        cin >> u >> v;
        a[i] = u - v;

    }
    sum = 1e4;
}

void solve() {
    inp();
    memset(dp, 0x3f, sizeof(dp));
    dp[0][BASE] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = -sum; j <= sum; j++) {
            dp[i][j + BASE] = min(dp[i][j + BASE], dp[i - 1][j - a[i] + BASE] + abs(j - a[i]) * z);
        }

        for (int j = -sum; j <= sum; j++) {
            dp[i][j + BASE] = min(dp[i][j + BASE], dp[i][j - 1 + BASE] + x);
        }
        for (int j = sum; j >= -sum; j--) {
            dp[i][j + BASE] = min(dp[i][j + BASE], dp[i][j + 1 + BASE] + y);
        }

    }
    cout << dp[n][BASE];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

:::

## Bài 3: [Xếp hộp](https://marisaoj.com/problem/368)
- Đề bài bảo các hộp chồng lên nhau không bắt buộc thứ tự từ $1$ đến $n$. Nếu có thứ tự thì dễ quá, nên ta sẽ làm cách nào để tìm được thứ tự của các vật để DP siêu dễ.
- Sort các thùng theo $w_i+c_i$, thùng nào có giá trị này lớn hơn được xếp ở dưới.
- Chứng minh: Với hai vật $i,j$, nếu $w_i+c_i>w_j+c_j$, ta chứng minh nếu xếp $j$ dưới $i$ sẽ không tối ưu bằng $i$ trên $j$:
+ Nếu thùng $i$ nằm dưới $j$, tải trọng tối đa của các thùng ngoài $j$ ra là $c_i-w_j$.
+ Nếu thúng $j$ nằm dưới $i$, tải trọng tối đa của các thùng ngoài $i$ ra là với $j$ nằm dưới $i$ là $c_j-w_i$.
+ $w_i+c_i>w_j+c_j \Leftrightarrow c_j-w_i<c_i-w_j$ nên để $i$ nằm dưới $j$ sẽ tối ưu hơn.

Code
:::spoiler

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 5005;

int n;
pi a[maxn];

int dp[maxn][maxn], ans = 0;

#define w first
#define limit second

inline void mini(int &a, int b){
    a = min(a, b);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    setinf(dp);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].w;
    for(int i = 1; i <= n; i++) cin >> a[i].limit;

    sort(a + 1, a + n + 1, [&](const pi &a, const pi &b){
        if(a.w + a.limit == b.w + b.limit) return a.w < b.w;
        return a.w + a.limit > b.w + b.limit;
    });

    setinf(dp);

    for(int i = n; i >= 1; i--){
        dp[i][1] = min(dp[i][1], a[i].w);
        for(int j = 1; j <= n; j++){
            mini(dp[i - 1][j], dp[i][j]);
        }
        for(int j = 1; j <= n - i + 1; j++){
            if(dp[i][j] == inf64) continue;
            if(dp[i][j] <= a[i - 1].limit)
            mini(dp[i - 1][j + 1], dp[i][j] + a[i - 1].w);
        }
    }

    for(int i = n; i >= 1; i--){
        if(dp[1][i] != inf64) return cout << i , 0;
    }
    cout << 0;
}

:::