范围$100$
比较裸的式子
$f[i][j]$表示枚举到第$i$位有没有和为$j$方案
只有$0$或$1$ $f[i][j]=f[i-1][j-val*val]$
答案$\sum\limits f[n][i]$
范围$1000000$$((1-100)^2 *100)$
复杂度爆炸,可以滚动数组,得17分
考虑优化,$bitset$,
$bitset$表示实际值是否可以凑出
$f[i]|=f[i-1]<<(val*val)$
注意我们这里维护的是一个类似前缀和的东西
例如(举个例子不保证正确性)
你$f[1]$二进制下$11$,(即可凑出1 , 2)
然后你$f[2]$可以取$1$,那么你在第二位可以凑出就是$011$(可凑出2,3)
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1111111 bitset<A> f[101]; ll a[101],b[101]; ll n; int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]); for(ll i=1;i<=n;i++){ for(ll j=a[i];j<=b[i];j++){ if(i==1) f[i][j*j]=1; else f[i]|=f[i-1]<<(j*j); } } printf("%lld\n",1ll*f[n].count()); }
原文：https://www.cnblogs.com/znsbc-13/p/11574209.html
