首页 > 其他 > 详细

NC13885 Music Problem

时间:2020-10-02 00:19:48      阅读:2      评论:0      收藏:0      [点我收藏+]

标签:const   继续   spa   简单   tps   表示   

简单瞎搞题 类似

状态表示:\(f[i][j]\) 表示前\(i\)个数能组成的模3600的数,\(f\)只有0、1两种状态
答案:判断\(f[n][0]\)是否为真即可

时间复杂度:\(O(T*n*3600)\),显然无法接受

优化:将bool数组替换成bitset

const int N=1e5+10;
int a[N];
bitset<7200> f[2];
int n;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        f[0].reset();

        cin>>n;

        for(int i=1;i<=n;i++) cin>>a[i];

        for(int i=1;i<=n;i++)
        {
            f[i&1]=f[i-1&1];
            f[i&1] |= f[i-1&1]<<(a[i]%3600) | (f[i-1&1]<<(a[i]%3600)>>3600);
            f[i&1][a[i]%3600]=1;//一定要放在或操作后面,若对第i个先置1再或操作转移,相当于加上了第i个物品放两次的状态
        }

        if(f[n&1][0]) puts("YES");
        else puts("NO");
    }
    //system("pause");
}

继续对滚动数组优化:

const int N=1e5+10;
int a[N];
bitset<7200> f;
int n;
 
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        f.reset();
 
        cin>>n;
 
        for(int i=1;i<=n;i++) cin>>a[i];
 
        for(int i=1;i<=n;i++)
        {
            f|=f<<(a[i]%3600) | (f<<(a[i]%3600)>>3600);
            f[a[i]%3600]=1;
        }
 
        if(f[0]) puts("YES");
        else puts("NO");
    }
    //system("pause");
}

NC13885 Music Problem

标签:const   继续   spa   简单   tps   表示   

原文:https://www.cnblogs.com/fxh0707/p/13759040.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号