Vijos 1386 矿工配餐 解题报告

由于食物的分配顺序是确定的，所以可以以前面i个食物作为阶段划分。而只有每个煤矿的最后两个食物的类型会对后面造成影响，因此可以用状态f[i,j,k,l,m]表示分配到第i个食物时，第一个煤矿最后两个食物依次是j和k，第二个煤矿最后两个食物依次是l和m时的总最大产量。

状态转移方程：

放在第一个煤矿：f[i+1,k,food[i+1],l,m]:=max(f[i+1,k,food[i+1],l,m],f[i,j,k,l,m]+dif(j,k,food[i+1]));

放在第二个煤矿：f[i+1,j,k,m,food[i+1]]:=max(f[i+1,j,k,m,food[i+1]],f[i,j,k,l,m]+dif(l,m,food[i+1]));

由于f[i+1]只与f[i]有关，所以可以用滚动数组将空间复杂度降到O(2*4^4)。

R1141347 Accepted 100 From IwfWcf－ P1386 FPC Vivid Puppy 2009-2-10 16:47:16