problem

Input

第一行一個數n (1<=n<=100)
然后n行，每行兩個數表示ai,bi (1<=ai,bi<=100)

Output

輸出一行一個數表示答案。

Input

5
1 2
2 3
3 4
4 5
5 6

Output

26

Limitation

2s 256MB

傳送門傳送門傳送門傳送門

思路

因為平方和最大只有1000000,所以可以開數組進行標記是否有，比如bool數組，然后dp

for(int i=2;i<=n;++i){for(int j=1;j<=1000000;++j){if(dp[i-1][j]){for(int k=lr[i].l;k<=lr[i].r;++k){dp[i][j+k*k]=1;}}}}

但時間復雜度為100^5

考慮用bitset優化常數

關于bitset可以參考bitset頭文件簡介

---

每一個bitset設為1e6，需要1e2個這樣的單位
對于每一個單位在原先

for(int j=1;j<=1000000;++j)

進行優化：

dp[i]=dp[i] | dp[i-1]<<(k*k);

剛開始bitset全是0，后來全是1，所以可以認為常數是1/2
那么時間復雜度就是O( 100^5 / 128 )

代碼示例

#include<bits/stdc++.h> using namespace std;const int maxn=101; const int maxm=1000010; int n;bitset<maxm> dp[maxn];struct qu{int l,r; }lr[maxn];void slove() {for(int i=lr[1].l;i<=lr[1].r;++i){dp[1][i*i]=1;}/*原代碼for(int i=2;i<=n;++i){for(int j=1;j<=1000000;++j){if(dp[i-1][j]){for(int k=lr[i].l;k<=lr[i].r;++k){dp[i][j+k*k]=1;}}}}*///優化for(int i=2;i<=n;++i){for(int k=lr[i].l;k<=lr[i].r;++k){dp[i]=dp[i] | dp[i-1]<<(k*k);}} }int main() {ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;++i){cin>>lr[i].l>>lr[i].r;}slove();int ans=dp[n].count();cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的17AHU排位赛2 F题（bitset优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。