https://www.nowcoder.com/acm/contest/132/C
参考博客 https://blog.csdn.net/Flanoc/article/details/74276015
对于这种关于某个数能不能取的dp,我们可以用bitset来优化。
bitset本质上是维护二进制,而又由于二进制的特殊性,完全可以当作一个bool型数组。
bitset f//相当于bool f[N]
f.any()//整个二进制中是否有一个位置被置为1
f.none()//是否整个f中所有位上都是0
f.count()//二进制中1的个数
f.set()//将二进制各个位置全都置为1
f.set(i)//相当于f[i]=1
f.reset()//将二进制各个位置全都置为0
f.reset(i)//相当于f[i]=0
f.flip()//将二进制所有位取反
f.flip(i)//相当于f[i]^=1
而bitset的常数是远小于直接用bool型数组进行维护的。
所以这道题用bitset来维护的话就很好搞了。
#include<bits/stdc++.h>
using namespace std;
bitset<100*100*100+7>dp[200];
int a,b;
int main()
{
ios::sy
int n;
cin>>n;
dp[0][0] = 1;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
dp[i].reset();
for(int j=a;j<=b;j++)
{
dp[i]|=dp[i-1]<<(j*j);
}
}
printf("%d\n",dp[n].count());
return 0;
}