注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1059  

2012-07-12 14:38:09|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1059
多重背包+二进制优化
刚开始用多重背包做了,然后就悲剧的超时了。。。后来再怎么优化也不行,没想到用二进制进行优化,参看了大牛的分析,才明白原来可以用二进制进行优化,简单的说就是如果有价值为i的物品有n个,可以把n拆成几个物品,分别是1,2,4,8……n-2^k+1,例如13可以拆成13=1+2+4+6
注意:刚开始没明白为什么可以这么拆,后来想明白了,因为任何一个数都能拆成1,2,4,8……n-2^k+1之和,例如3本来可以是1+1+1,但是3可以拆成1+2,这样比原来的优化了一步,把原来复杂度为O(V*Σn[i])的降到O(V*Σlog n[i]),优化了不少

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-12
 *      Author: fudq
 */
//多重背包+二进制优化
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
#define N 120020
bool t[N];
int a[10];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int i,j,k,s,temp,res,cas=1;
    while(1)
    {
        for(i=1,s=0;i<=6;i++)
        {
            scanf("%d",&a[i]);
            s+=a[i]*i;
        }
        if(s==0)
            break;
        printf("Collection #%d:\n",cas++);
        if(s%2==1)
        {
            printf("Can't be divided.\n\n");
            continue;
        }

        //
        memset(t,false,sizeof(t));
        t[0]=true;
        for(i=1;i<=6;i++)
        {
            if(t[s/2])
                break;
            temp=a[i];
             for(j=1;j<=a[i];j*=2)
             {
                 for(k=s/2;k>=j*i;k--)
                     if(t[k-j*i])
                         t[k]=true;
                 a[i]-=j;
             }
             if(a[i])
             {
                 res=(temp-j+1)*i;
                 for(k=s/2;k>=res;k--)
                     if(t[k-res])
                         t[k]=true;
             }
        }
        if(t[s/2])
            printf("Can be divided.\n");
        else
            printf("Can't be divided.\n");
        printf("\n");
    }
    return 0;
}
  评论这张
 
阅读(405)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018