DP State Design

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Problem: Given an array of non-negative integers, pick a subset with no two adjacent
5
// elements to maximize the sum. Demonstrates 1D DP state: dp[i] = best using first i items.
6
7
long long maxNonAdjacentSum(const vector<int>& a) {
8
    int n = (int)a.size();
9
    if (n == 0) return 0;
10
11
    // dp[i] = best answer considering first i elements (a[0..i-1])
12
    // Transition: dp[i] = max(dp[i-1], dp[i-2] + a[i-1])
13
    long long prev2 = 0;       // dp[0]
14
    long long prev1 = a[0];    // dp[1]
15
16
    for (int i = 2; i <= n; ++i) {
17
        long long take = prev2 + a[i-1];
18
        long long skip = prev1;
19
        long long cur = max(take, skip);
20
        prev2 = prev1;
21
        prev1 = cur;
22
    }
23
    return prev1;
24
}
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    int n; cin >> n; // e.g., 6
31
    vector<int> a(n);
32
    for (int i = 0; i < n; ++i) cin >> a[i];
33
    cout << maxNonAdjacentSum(a) << "\n";
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// 0/1 Knapsack: maximize value with capacity W, each item can be taken at most once.
5
// Logical state: dp[i][w] = best value using first i items with capacity w.
6
// Implementation: 1D rolling array dp[w], iterating w in decreasing order to prevent reuse.
7
8
long long knapsack01(const vector<int>& wt, const vector<int>& val, int W) {
9
    int n = (int)wt.size();
10
    vector<long long> dp(W + 1, 0); // dp[w] == dp[i][w] for current i after processing
11
12
    for (int i = 0; i < n; ++i) {
13
        // Decreasing w ensures each item i is used at most once
14
        for (int w = W; w >= wt[i]; --w) {
15
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
16
        }
17
    }
18
    return dp[W];
19
}
20
21
int main() {
22
    ios::sync_with_stdio(false);
23
    cin.tie(nullptr);
24
25
    int n, W; cin >> n >> W; // e.g., n=4, W=7
26
    vector<int> wt(n), val(n);
27
    for (int i = 0; i < n; ++i) cin >> wt[i] >> val[i];
28
    cout << knapsack01(wt, val, W) << "\n";
29
    return 0;
30
}
31

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given an n x n cost matrix cost[i][j], assign each worker i to a unique job j minimizing total cost.
5
// State: dp[mask] = minimum cost to assign the first popcount(mask) workers to the set of jobs indicated by 'mask'.
6
// Transition: try assigning the next worker to any unassigned job.
7
8
long long assignmentDP(const vector<vector<int>>& cost) {
9
    int n = (int)cost.size();
10
    int N = 1 << n;
11
    const long long INF = (1LL<<60);
12
    vector<long long> dp(N, INF);
13
    dp[0] = 0; // No workers assigned, no jobs used
14
15
    for (int mask = 0; mask < N; ++mask) {
16
        int i = __builtin_popcount((unsigned)mask); // next worker index
17
        if (i >= n) continue;
18
        for (int j = 0; j < n; ++j) {
19
            if (!(mask & (1 << j))) {
20
                int nmask = mask | (1 << j);
21
                dp[nmask] = min(dp[nmask], dp[mask] + cost[i][j]);
22
            }
23
        }
24
    }
25
    return dp[N - 1];
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    int n; cin >> n; // e.g., n <= 20 for feasibility
33
    vector<vector<int>> cost(n, vector<int>(n));
34
    for (int i = 0; i < n; ++i)
35
        for (int j = 0; j < n; ++j)
36
            cin >> cost[i][j];
37
38
    cout << assignmentDP(cost) << "\n";
39
    return 0;
40
}
41

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count integers x with 0 <= x <= N such that sum_of_digits(x) % m == 0.
5
// State components:
6
//  - pos: current index in the digit string (0..L)
7
//  - sum_mod: current digit sum modulo m (0..m-1)
8
//  - tight: are we restricted to digits <= N[pos]? (0/1)
9
//  - started: have we placed any non-leading-zero yet? (0/1), to treat leading zeros correctly
10
// Recurrence tries digits 0..limit and updates sum_mod only after we've started.
11
12
struct MemoKey {
13
    int pos, sum_mod, tight, started;
14
};
15
16
long long dfs(int pos, int sum_mod, int tight, int started,
17
              const string &S, int m,
18
              vector<vector<vector<vector<long long>>>> &dp) {
19
    if (pos == (int)S.size()) {
20
        // At the end: valid if started (we counted a number, possibly 0) and sum_mod == 0
21
        return (sum_mod % m == 0) ? 1LL : 0LL;
22
    }
23
    long long &res = dp[pos][sum_mod][tight][started];
24
    if (res != -1) return res;
25
    res = 0;
26
27
    int limit = tight ? (S[pos] - '0') : 9;
28
    for (int dig = 0; dig <= limit; ++dig) {
29
        int ntight = tight && (dig == limit);
30
        int nstarted = started || (dig != 0);
31
        int nsum = sum_mod;
32
        if (nstarted) {
33
            nsum = (sum_mod + dig) % m;
34
        } else {
35
            // Leading zeros do not contribute to sum
36
            // Keep nsum = sum_mod
37
        }
38
        res += dfs(pos + 1, nsum, ntight, nstarted, S, m, dp);
39
    }
40
    return res;
41
}
42
43
long long countSumDivisible(string N, int m) {
44
    // Pad N with no changes; we use its digits as the tight bound
45
    int L = (int)N.size();
46
    // dp dimensions: L x m x 2 x 2, initialized to -1
47
    vector<vector<vector<vector<long long>>>> dp(
48
        L, vector<vector<vector<long long>>>(
49
               m, vector<vector<long long>>(2, vector<long long>(2, -1))));
50
    return dfs(0, 0, 1, 0, N, m, dp);
51
}
52
53
int main() {
54
    ios::sync_with_stdio(false);
55
    cin.tie(nullptr);
56
57
    string N; int m; // Example: N = "1000", m = 3
58
    cin >> N >> m;
59
    cout << countSumDivisible(N, m) << "\n";
60
    return 0;
61
}
62