[分组背包] 牛客练习赛22C(bitset优化)

题面

  一共有 n个数，第 i 个数是 $x_i$ ,$x_i$ 可以取 $[l_i,r_i]$ 中任意的一个值。
设 $S=\sum {x_i}^2$, 求 S 种类数。
  

分析

  这一题主要用的是分类背包的思想，$dp[i][j]$表示的是考虑到第$i$个区间，S是否能取到$j$，取到为1，取不到为0。
  进行三重循环遍历(第一层区间数$n$，第二层$j$的取值可以到达$n^3$，第三层为区间中的每个数遍历为$n$)，总复杂度到达了$O(n^5)$。
  这样进行动态规划的话比较浪费时间和内存，因为每个状态只有01两种取值，因此可以用 bitset 进行优化， 将$1int$压成$1bit$。

  bitset的基本用法： (bitset可以进行各种位操作，以及$count，set$方法的使用)
  可以$dp[i]$表示第$i$个区间可以表示的S(S的最大取值为$10^6$,因此bitset最多需要$10^6$位), 对于区间中的每个数$j$,可以得出这样的转移方程$dp[i]|=dp[i-1]<<(j\ast j)$, 这样复杂度降到了 $O(n/32)$, 并且其中的位操作是更快的。
 最后答案即为$dp[n]$中1的个数，可以用$count()$方法得到。
  

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;

bitset<maxn> dp[102];
int n, l ,r;

int main()
{
    scanf("%d", &n);
    dp[0].set(0);             //第0位要置1
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &l, &r);
        for(int j = l; j <= r; j++)
            dp[i] |= dp[i-1]<<(j * j);
    }
    printf("%d\n", dp[n].count());
}