https://ac.nowcoder.com/acm/contest/24213/1035
-
一眼分组背包
f[i][j]:从前i个中选是否能组成j的集合。
属性：true / false
最后统计答案即可，但铁T -
利用bitset优化
f[i] |= f[i-1]<<(j * j) ,f[i]表示前i此选择组成的和的bitset形式。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
bitset<1000010> f[120];
int main(){
cin>>n;
int l,r;
for(int i = 1;i<=n;i++){
cin>>l>>r;
for(int j = l;j<=r;j++){
if(i==1){
f[i][j*j] = 1;
}
else{
f[i]|= (f[i-1]<<(j*j));
}
}
}
cout<<f[n].count();
}