题目大意

给定$n(n\le5\times10^{3})$个整数，问由这些整数通过“加法”操作，可以组成多少种数字？
其中，对于每个数$a_i$,$1\le a_{i}\le100$

初步思路

首先，暴力dfs肯定是不能通过的，我们可以考虑用存在性dp来解决。

存在性dp，即我们只需考虑这个状态是否能够实现，即用0/1来代替。

先考虑最基本的，我们假设$dp[i][j]$为到第$a_i$个数位置能否组成$j$。然后考虑转移方程，首先$dp[i-1][j]$为$1$的情况那么$dp[i][j]$肯定能达到，在当前基础上$j+a_i$的数值也能达到。

例如:$i-1$之前可以组成$1,2,3$,$a_i=2$，则对于$i$之前，$3,4,5$一定也可以达到。因此，我们借助倒推回去的思想可以得到状态转移方程:
$$dp[i][j]=(dp[i-1][j-a_i]|dp[i][j])$$
之所以要用或运算，是因为这两个状态只要其中一个为$1$就可以了，而或运算则正好适用于这个情况。
而这时候的空间复杂度为$5\times10^{3}\times5\times10^{3}\times100$，显然是过不了的

进一步思考

对于到$a_i$这一维度，其实是可以直接省掉的，以此来节省空间，但是对于时间复杂度来说，依然是过不了的。接下来，我们就可以用到$\texttt{bitset}$这个东西了。
$\texttt{bitset}$可以当作有很多二进制的集合，只支持位运算，而不支持加减乘除，支持随机访问。

$\texttt{bitset}$常用函数

  1. .count()统计1的数量
  2. .reset()全部重置为0
    以上的时间复杂度均为$O(n)$

解题

假设从左到右分别代表$…,3,2,1,0$能否组成，当前状态$\texttt{s}$为$11$,$a_i=1$,只需要将当前状态先左移1位变成$110$,再或起来变成$111$即代表能组成$2,1,0$($\texttt{Tips:}$从右往左为低位到高位)。显然达到了我们的需求，假如$a_i=5$,只需要左移5位再或起来即可。
因此，我们可以得到转移方程:
$$dp=dp|(dp<<a_i)$$
其中$\texttt{dp}$用$\texttt{bitset}$表示,故代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5,M = 5e5 + 5;
int n,a[N];
bitset<M> bs;
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)cin >> a[i];
    bs[0] = 1; //初始化代表可以表示0
    for(int i = 1;i <= n;i++)
    {
        bs |= (bs << a[i]);//状态转移
    }
    cout << bs.count();//统计1的个数即为答案
    return 0;
}