牛客——简单瞎搞题（bitsit优化DP）

UP:好像01的东西都会有些奇奇怪怪的优化，比如双端队列BFS就是一个很秀的算法。https://blog.csdn.net/weixin_45675097/article/details/106265696

前言：（bitset的学习）

很容易看出来是背包问题，我们用dp[i] [j] 表示只由前i个数字构成j，分界点就是第i个数字是否选择。当dp[i-1] [j-x*x ]==1时可以转移到dp[i] [j] 。但这样的话复杂度就是O（n^5），有些爆表了。

根据雨巨的思路，可以用bitset来优化，bitset就是一个只含有0和1的类型，类似bool数组，但是空间出奇的小。

常用函数：

bitset<maxn>tmp;///定义的时候就需要初始化位数
tmp.size();///返回位数
tmp.count;//返回1的个数

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
bitset<maxn>tmp,res;
int main(){
    int n;cin>>n;
    res[0]=1;
    for(int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        for(int j=l;j<=r;j++)
            tmp|=res<<(j*j);
        res=tmp;
        tmp.reset();
    }
    cout<<res.count()<<endl;
    return 0;
}