17AHU排位赛2 F题(bitset优化)

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;
}




评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)