时间限制(普通/Java):2000MS/6000MS 内存限制:65536KByte
总提交: 8 测试通过:5
描述
一共有 n个数，第 i 个数是 xi ，其中xi 可以取 [li , ri] 中任意的一个值。
设 ，求 S 种类数。
输入
第一行一个数n，接下来有n行，每行两个整数li，ri。
1<=n，li，ri<=100，数据保证li<=ri。
输出
输出一行一个数表示答案。
样例输入
5
1 2
2 3
3 4
4 5
5 6
样例输出
26
解析：用bitset优化，dp，每输入一个范围，就是在前面已经计算的基础上加上这次范围内的数，每一次都加上l 到 r的范围的值，用|代替加法，<<i*i把答案加入到数组中。状态转移方程是a[i]|=a[i-1]<<(i*i);
#include "bits/stdc++.h"
#define ll long long
using namespace std;
inline void read(int &x)
{
x=;char c=getchar();
while(c<'' || c>'')c=getchar();
while(c>='' && c<=''){
x=x*+c-'';
c=getchar();
}
}
inline void write(int x)
{
int y=,len=;
while(y<=x) {y*=;len++;}
while(len--){y/=;putchar(x/y+);x%=y;}
}
bitset<>a,b;
int main()
{
int n,l,r;
read(n);
b[]=;
while(n--)
{
read(l);read(r);
a.reset();
//b.reset();
//b[0]=1;
for(int i=l;i<=r;++i)
{
a|=b<<(i*i);
}
b=a;
}
printf("%d\n",b.count());
}