简单瞎搞题
简单瞎搞题
https://ac.nowcoder.com/acm/problem/17193
看题目，没找到什么规律；而且每个区间正好可以看成一个空间，分别从每个空间取出一个物品，满足题意；所以分组背包；
dp[i][j]到第i个空间时，值是否可达到j；显然这样会超内存；
对于每个dp值，只存在0，1；所以考虑bitset优化；
到达第i个位置dp [ i ] = dp [ i ] | ( dp [ i - 1 ] << ( x * x ) )；
如果第i个位置为一，则i这个数可被表示；往左移动xx位，也就相当于加上xx
#include<bits/stdc++.h>
using namespace std;
const int maxn=1100000;
struct node{
int l,r;
}node[120];
bitset<maxn> dp[120];
int main()
{
int n;
cin>>n;
dp[0].set(0);
for(int i=1;i<=n;i++) cin>>node[i].l>>node[i].r;
for(int i=1;i<=n;i++)
{
for(int k=node[i].l;k<=node[i].r;k++)
dp[i]|=(dp[i-1]<<(k*k));
}
cout<<dp[n].count();
}
