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

*题目描述 *
一共有 n个数，第 i 个数是 xi
xi 可以取 [li , ri] 中任意的一个值。
求 种类数。

输入描述:
第一行一个数 n。
然后 n 行，每行两个数表示 li,ri。

输出描述:
输出一行一个数表示答案。

思路
令 dp[i][j]表示为第 i 次选择时，和为 j的情况是否出现过
但是内存方面需要 1e8 的 int 内存，显然是不可接受的
那么我们考虑用 bitset优化一下，有递推方程 "图片标题")
代表第 i次选择的时候是否能从当前状态转移到和为 j的状态
代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
bitset<N>dp[105];
int main(){
    int n;
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        for(int j=l;j<=r;j++)
          dp[i]|=(dp[i-1]<<(j*j));
    }
    cout<<dp[n].count();
}