背包问题（完全背包）

前言：背包问题，一定要抽象出背包问题

题目地址

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;void solve() {i64 n, m, t;std::cin >> n >> m >> t;std::vector<i64> a(m + 1);for (i64 i = 1; i <= m; i++) {std::cin >> a[i];}t -= n;if (t < 0) {std::cout << 0 << '\n';return;}std::sort(a.begin() + 1, a.end());std::set<int> st;for (int i = 1; i < m; i++) {st.insert(2 * (a[i + 1] - a[i]));}std::vector<bool> dp(t + 1, 0);dp[0] = 1;for (auto it : st) {for (int i = it; i <= t; i++) {dp[i] = dp[i] | dp[i - it];}}for (int i = t; i >= 0; i--) {if (dp[i]) {std::cout << i + n << '\n';return;}}
}signed main() {std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);i64 t = 1; std::cin >> t;while (t--) {solve();}
}