Knapsack Problems

Knapsack problems represent one of the foundational dynamic programming concepts. Typically, either weight or value is represented as a dimension in the state space, with the smaller dimension usually chosen for optimization. When both weights and values are large, standard approaches may fail due to computational constraints. In such cases, specialized optimizations like binary compression become necessary.

A notable example is the "Dream Island Pearl" problem which demonstrates how to compress states using binary decomposition, focusing only on the last few bits to save memory. For multi-dimensional knapsacks involving n dimensions, it's common practice to collapse n-1 dimensions into the state representation.

Operations like insertion and deletion in knapsack problems are inverse operations. This principle can be leveraged in scenarios involving range queries, where techniques like Mo's algorithm might be applicable.

Changes in knapsack formulations typically involve modifying the problem statement, refining state definitions, or redefining what the final answer represents. Adapting to these variations requires careful analysis and flexible thinking.

Bitmask Dynamic Programming

Bitmask DP generally involves encoding small sets or states within a limited bit space. A specific technique appears in problems like Zoo and School Cafeteria, where the approach records transitions dynamically.

The subset enumeration operation in bitmask DP runs in O(3^n), as demonstrated in CF1209E2. While this complexity may seem prohibitive, if constant factors are small enough, practical performance can still be acceptable. However, more efficient methods exist—though they may require careful tuning to pass tight time limits.

Two advanced patterns emerge:

1. Subset Sum Computation: Computing g_i = ∑_{i&j=j} f_j can be optimized using high-dimensional prefix sums, achieving O(n·2^n) complexity.
2. AND Convolution: This involves maintaining suffix sums and applying reverse operations, though less commonly tested.

Digit DP

Digit DP typically addresses counting problems over ranges [l, r]. The core idea is to incorporate digit positions into the DP state, since later digits have minimal impact from earlier ones, or their influence can be precomputed.

Implementation strategies include:

• Separating each digit position
• Processing from right to left
• Calculating suffix values
• Using recursive DFS with parameters indicating whether the current number matches the upper bound exactly

Tree DP

Tree DP techniques are well-understood and widely applied. Key concepts involve traversing trees bottom-up or top-down, depending on the nature of dependencies between nodes and subtrees.

Interval DP

Interval DP uses states of the form dp[l][r] to represent subproblems. The minimum complexity is O(n²).

Common transition patterns include:

1. Enumerating split points: divide into two independent subproblems
2. Time complexity becomes O(n³) when splitting is required

For circular variants, breaking the cycle into a linear chain by doubling its length often helps.

An alternative approach exists when transitions depend only on adjacent intervals [l+1,r] or [l,r-1]. In such cases, no middle point enumeration is needed, reducing complexity to O(n²). Examples include bracket sequence problems like CSP-S2021T2.

DP Optimization Techniques

Data Structure Optimization

When standard DP transitions are involved, identifying appropriate data structures is crucial for optimizasion.

Monotonic Queue Optimization

This technique applies when the current DP value depends on a range of previous values with fixed components. If earlier elements are dominated by later ones, they can be discarded.

Monotonic Queue for Multiple Knapsack

Consider the recurrence:

dp[j] = max(dp[j - k*v[i]] + k*w[i])

Since elements with identical modulo v[i] affect eachother, we process based on remainder classes. After substitution, the equation becomes:

dp[q*v[i] + mo] = max(dp[(q-k)*v[i] + mo] + k*w[i])

Letting k = q - k gives us:

dp[q*v[i] + mo] = max(dp[k*v[i] + mo] - k*w[i]) + q*w[i]

This allows monotonic queue optimization with O(nV) complexity.

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 2e4 + 10, inf = 0x3f3f3f3f;

int n, m, w[N], v[N], s[N];
int f[N], front, tail;
pair<int, int>Q[N * 5];

int main() {
    read(n, m);
    for(int i = 1; i <= n; ++i) {
        read(v[i], w[i], s[i]);
        if(m / v[i] < s[i]) s[i] = m / v[i];
        for(int mo = 0; mo < v[i]; ++mo) {
            front = 1; tail = 0;
            for(int k = 0; k <= (m - mo) / v[i]; ++k) {
                while(front <= tail && Q[front].second < k - s[i]) front++;
                while(front <= tail && Q[tail].first <= f[k * v[i] + mo] - k * w[i]) tail--;
                Q[++tail] = {f[k * v[i] + mo] - k * w[i], k};
                f[k * v[i] + mo] = Q[front].first + k * w[i];
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

CF372C Watching Fireworks is Fun

This problem defines dp[i][x] as maximum happiness at time i at position x.

Transition:

dp[i][x] = max(dp[i-1][y]) + b[i] - |a[i] - x|

Where y ranges from [x - (t[i]-t[i-1])*d, x + (t[i]-t[i-1])*d].

Monotonic queues handle sliding window maximum efficiently.

#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 150005, inf = 0x3f3f3f3f;

typedef long long ll;
int n, m, d;
ll a[N], b[N], t[N];
ll dp[2][N];

signed main() {
    read(n, m, d);
    int p = 0;
    for(int i = 1; i <= m; ++i) {
        read(a[i], b[i], t[i]);
        int now = 0;
        deque<pair<int, int> >Q;
        for(int j = 1; j <= n; ++j) {
            while(now < j + (t[i] - t[i - 1]) * d && now < n) {
                ++now;
                while(!Q.empty() && Q.back().first <= dp[p ^ 1][now]) Q.pop_back();
                Q.push_back(make_pair(dp[p ^ 1][now], now));
            }
            while(!Q.empty() && Q.front().second < (j - (t[i] - t[i - 1]) * d)) Q.pop_front();
            dp[p][j] = Q.front().first + b[i] - abs(j - a[i]);
        }
        p ^= 1;
    }
    long long maxx = 0xcfcfcfcfcfcfcfcf;
    for(int i = 1; i <= n; ++i) maxx = max(maxx, dp[p ^ 1][i]);
    cout << maxx << endl;
    return 0;
}

Slope Optimization

Slope optimization is used when DP expressions take the form:

dp[i] = min/max {dp[j] ± f(j) × g(i)} + i-dependent terms

Here, g(i) is treated as slope. The key insight is to maintain a convex hull of valid (x, y) points where x = f(j) and y = dp[j] + f(j)².

P3195 Toy Box Packing

Problem: Minimize sum of squared differences of segments.

Transformed DP:

dp[i] = min{dp[j] + (sum[i] - sum[j] - L)²}

After algebraic manipulation:

dp[i] = min{dp[j] + sum[j]² - 2*sum[j]*sum[i]'} + sum[i]'²

Where sum[i]' = sum[i] - L. This leads to the form:

dp[i] = min{y - k*x} + sum[i]'²

Maintain a lower convex hull of points (x, y) where x = sum[j], y = dp[j] + sum[j]².

Advanced Techniques

Emiya's Dinner Problem

In some cases, instead of tracking full three-dimensional states dp[i][j][k], we can reduce the problem to tracking difference j - k. Since we're interested in j > k, we can equivalently track j - k > 0, simplifying the state space significantly.