P1441 砝码称重（01背包+枚举子集）

思路： 用$01$背包求$n$个数组成不同数的方案数，$dp[i]$代表组成能否组成$i$，然后用枚举子集求去掉$m$个数的状态集合，来枚举最大方案。

参考代码：

/* * @Author: vain * @Date: 2020 * @LastEditTime: 2020-10-07 18:44:42 * @LastEditors: sueRimn * @Description: 学不会 dp 的 fw * @FilePath: \main\demo.cpp */ #include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> //#include <unordered_map> using namespace std; typedef long long ll; #define ll long long //typedef unsigned long long uint; const int N = 5000 + 20; const int maxn = 1e5 + 20; const int mod = 998244353; int cnt, head[maxn], pos[maxn]; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p>> q; //int sum[maxn]; double Max(double a, double b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; } int lowbit(int x) { return (x) & (-x); } //map<int, int> vis; //unordered_map<int,int>vis; ll ksm(ll a, ll b) { ll res = 1; for (; b;) { if (b & 1) res = (res * a) % mod; b >>= 1, a = a * a % mod; } return res; } int read(int &v) { int k = 1; v = 0; int c = getchar(); while (c < '0' || c > '9') { if (c == '-') k = 0; c = getchar(); } while (c >= '0' && c <= '9') v = (v << 3) + (v << 1) + (c - 48), c = getchar(); if (k == 0) v = -v; return c; } int n, dp[2005], m, a[25], st[maxn * 10], ns, Maxs; ll ans; void init() { for (int i = 0; i < (1 << n); i++) { int sum = 0; for (int j = 0; j < n; j++) { if ((i >> j) & 1) sum++; } if (sum == m) st[ns++] = i; } } void slove(int x) { memset(dp, 0, sizeof dp); dp[0] = 1; ll Ma = 0; for (int i = 0; i < n; i++) { if ((x >> i) & 1) continue; for (int j = Maxs; j >= a[i]; j--) { if (dp[j - a[i]] && (!dp[j])) dp[j] = 1, Ma++; } } if (Ma > ans) ans = Ma; } int main() { read(n), read(m); init(); for (int i = 0; i < n; i++) read(a[i]), Maxs += a[i]; for (int i = 0; i < ns; i++) slove(st[i]); printf("%lld\n", ans); }