简单瞎搞题

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

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

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

思路:
其实是个背包。有n个组，每组选一个数，问最后背包能装的体积有多少种方案。
直接分组背包求解的话。n组，每组最多n个数，最大体积为n^3,复杂度为n^5,显然会TLE。
所以考虑用bitset优化，复杂度为

#include<bits/stdc++.h>
using namespace std;
bitset<1005000> a,b;
int main(){

    int n;cin>>n;
    a[0]=1;
    while(n--){
        int l,r;
        cin>>l>>r;
        b.reset();
        for(int i=l;i<=r;i++) b |= a<<i*i;
        a=b;
    }
    cout<<a.count();
    return 0;
}

顺手写了一发dp的tle代码

#include<bits/stdc++.h>
using namespace std;
bool dp[1000005];
int main()
{
    dp[0]=1;
    int n;
    cin>>n;
    int flag=0;
    while(n--)
    {
        int l,r;
        cin>>l>>r;
        for(int i=1000000;~i; i--)
        {
            if(dp[i])
            {
                for(int j=l; j<=r; j++)
                {
                    dp[i+j*j]=1;
                }
                dp[i]=0;
            }
        }
    }
    int ans=0;
    for(int i=1; i<=1000000; i++)
        ans+=dp[i];
    cout<<ans;

    return 0;
}