P2704 [NOI2001] 炮兵阵地

考虑好在哪里放比较好。

当前状态只与上两行有关系，因此压两行，考虑上一行状态。

有一个滚动数组优化技巧,如果留 $n$ 位， $f_{i \mod n}$ ，从 $0$ 开始计数。

f_{L,S,i}=\max(f_{L,S,i},f_{FL,L,i-1}+sum_S);

设山丘表示为 $1$ ，平原为 $0$ ，与为 $0$ 表示合法，因为有山丘当着不怕。

只考虑以当前点的整个上面。

每次皆以合法转移，绝对行。

总结：关键再判断不合法状态

P3092 [USACO13NOV] No Change G

二分+状压。

只与硬币的放置状态有关，那我们考虑状态之间的转移。

对于某个状态从他的子集转移，子集一定是满足条件的，因为从小到大，必然是可以转移的。

$dp_i$ 当前存储的最优状态下，可以到达的最右状态。

$f_i$ 当前状态下通过确定顺序能购买的花费硬币总代价。

顺序是通过子集最优继承的。

问题本质还是最优决策，决策量很小，那肯定是考虑状态枚举。

对于每个状态我们保留了最优决策后的最大贡献。

决策状态的转移，就是这么妙，考虑最终状态的所有可能性我们只有 $2^m$ 种状态因此不管了状压稳过。

还是每次都是小集合对大集合的贡献。

考虑决策量的数量印象我们最后的答案。

还是关注状态的选取只与当前的位置有关，上一个选择的在哪里有关。

那么我么就设一个可转移的状态 $f_{i,j,k}$ 前 $i-1$ 已经打完，当前含自己后的 $7$ 位并且保证合法状态 $S$ ，当前最后选的是 $i+k$ ， $k \in [-8,7]$ ，前后都得含。

那么合法转移 $j\And1==1$ 可转移到 $f_{i+1,j>>1,k-1}=f_{i,j,k}$ 。

考虑据上一个为 $0$ 的位置，那么下一个就是距离 $-1$ 的位置。

剩下的就考虑在之后的状态中转移。

挑一个不存在的，找一下上个位置可以进行的最远区间，然后从上一个转移就好。

递推一直是前进的，因此是正确的。

考虑状态压缩加反演。

枚举子集的子集去转移状态。

请注意状压都是从小的最优状态转移过来的

__END__