简单瞎搞题

先看题目：https://ac.nowcoder.com/acm/problem/17193
题目描述：
略
解题思路：
暴力枚举总共有100^100次方种情况，考虑使用dp。那么状态定义为什么呢？如果定义为dp[i][j]表示前i项有没有构成j这个数字，那么状态转移方程就变得很麻烦了，首先，开个1e8的数组就很大了，其次，每次要添一个数都需要for循环一遍，很麻烦，空间时间复杂度都很高。bitset在解决这类问题上就很好用！

定义：

bitset<MAX> dp[101]; //dp[i]表示前i项构成了哪些数字，比如前i项能构成16，那么第16位就为1

状态转移也很好写，依题意，需累加第i项区间中的数j的平方，那么只需把dp[i-1]的所有的1都左移(j*j)
|(或)运算符只有全是0的情况下才是0

状态转移方程：

dp[i] |= dp[i-1]<<(j*j);

代码：

#include<bits/stdc++.h>
using namespace std;
const int M = 1e6+7;
bitset<M> dp[101];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)  {
        int l, r;
        scanf("%d%d",&l,&r);
        dp[0] = 1;
        for(int j = l; j <= r; j++) {
            dp[i] |= dp[i-1]<<(j*j);
        }
    }
    printf("%d\n",dp[n].count());
}