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