2009年2月14日星期六

Vijos 1426 兴奋剂检查 解题报告

这道题本质就是n维背包,但由于每个背包的容量不确定,因此不能使用朴素的状态储存方式,必须对状态进行压缩。题目给了一个提示V1*V2*V3*...*Vm<=5000000,这实际上可以理解为如果将各个背包限制容量先以二进制的方式表示,再将各个背包顺次连接成一个“大背包”,所需要的二进制数转化为十进制不超过5000000。状态转移时需要应用一些位运算的处理操作,个人感觉这道题比较具有代表性,因此把状态转移部分的代码贴出来:

for i:=1 to n do
    for j:=s-v[i] downto 0 do
      begin
        if f[j]+a[i]<=f[j+v[i]] then continue;
        success:=true;
        for k:=1 to m do
          if b[i,k]+(j-(j shr l[k] shl l[k])) shr l[k-1]>c[k] then
            begin
              success:=false; break;
            end;
        if success then f[j+v[i]]:=f[j]+a[i];
      end;

其中s表示的是m个背包都是最大数值时的状态,v[i]表示第i个物品所需的背包空间的状态,b[i,k]表示的是第i个物品所需的第k个背包的容量,l[k]表示前k个背包的状态包含的二进制位数,f[i]表示i状态时背包所能获得的最大价值。

R1145830 Accepted 100 From IwfWcf- P1426 FPC Vivid Puppy 2009-2-14 20:49:55

9 条评论:

  1. oakley sunglasses wholesale, http://www.oakleysunglasses-wholesale.us.com/
    ugg boots, http://www.uggbootscheap.eu.com/
    ralph lauren uk, http://www.ralphlaurenoutletuk.org.uk/
    thomas sabo uk, http://www.thomassabos.co.uk/
    michael kors factory outlet, http://www.michaelkorsfactoryoutletonline.com/
    michael kors factory outlet, http://www.michaelkorsfactoryoutlets.in.net/
    michael kors handbags, http://www.michaelkorshandbagsoutletstore.us.com/
    oakley sunglasses, http://www.oakleysunglasseswholesale.in.net/
    oakley, http://www.occhialioakleyoutlets.it/
    oakley sunglasses wholesale, http://www.oakleysunglasseswholesale.us.com/
    tory burch shoes, http://www.toryburchshoesoutlet.com/
    pandora jewelry, http://www.pandorajewelryoutlet.us.com/
    hollister uk, http://www.hollistershirts.co.uk/
    cheap nba jerseys, http://www.nbajerseys.net/
    fitflop, http://www.fitflop.in.net/
    louis vuitton, http://www.borselouisvuittonoutlet.it/
    juicy couture outlet, http://www.juicycoutureoutlet.net/
    coach outlet, http://www.coachoutletus.us/
    oakley sunglasses, http://www.oakley.in.net/
    rolex watches uk, http://www.rolexwatches-uk.co.uk/
    longchamp outlet, http://www.longchampoutlet.name/
    michael kors bags, http://www.michaelkorsbags.uk/
    michael kors outlet, http://www.michaelkors-outlets.us.com/
    ugg boots, http://www.uggbootsclearance.in.net/
    nike air max shoes, http://www.nikeairmaxshoess.co.uk/
    links of london, http://www.linksoflondons.co.uk/
    michael kors outlet, http://www.michaelkorsoutletusa.net/
    designer handbags, http://www.designerhandbags.us.com/
    ray ban sunglasses, http://www.raybansunglass.co.uk/
    1003maoqiuyun

    回复删除
  2. تستخدم شركة الاول افضل معدات تنظيف المنازل فيمكنك الاستعانة بنا لتحظى بافضل تنظيف للمنازل ولدينا فروع تغطى جميع المملكة فشركة الاول تعد افضل
    شركة تنظيف بمكة
    وافضل شركة تنظيف بالاحساء


    افضل شركة تنظيف سجاد بالرياض



    صيانة مكيفات بالرياض

    回复删除
  3. investigate this site description look at this now webpage important source pop over to this website

    回复删除

 
Creative Commons License
除非另有声明,本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。