【每日一题】5月20日 简单瞎搞题

一共有 n个数，第 i 个数是
可以取 中任意的一个值。
设 ，求 S 种类数。

分析:分组背包问题，的值表示前i个数是否能表示j, 我们要求最后能表示的数的种类数，就是求
.
考虑每一个dp状态只有两种0和1.那么我们可以用bitset优化背包，将第二维的值变成二进制下1的位置.那么转移状态:
.
那么最后的答案就是 的1的个数，直接调用count()计算即可。
另外附一题同样的bitset背包优化的题.

https://ac.nowcoder.com/acm/contest/4912/C
题解暂时鸽了

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+10;

bitset<maxn> dp[102];
int n;

int main()
{
    scanf("%d",&n);dp[0].set(0);
    for( int i=1;i<=n;i++ )
    {
        int l,r;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());
}