Dies Irae

1013是说有三种兵器，每种有一个质量和一个体积还有一个防御值，然后要商队来运输，商队的每个人只能携带不超过一定质量和体积的兵器。三种兵器以某个比例和起来用可以增加防御值。求一个按照商队的限制可以得到的最大防御值。

方法应该是不难，可以用一个4维的布尔数组，第1维是商队，剩下3维表示状态，true表示这种状态可达。不过这个状态表示的效率不论空间还是时间都极低，考虑到这个布尔数组的第四维只有最大值一个点是有用的，改进一下，用3维的数组，1维是商队，剩下两维表示前两种兵器的状态，然后里头存的是在前两种兵器以及当前这个人的限制情况下，可以拿的第三种兵器的最大值。这样就可以有效降低复杂度了。

问题就是老是调不过，调不过阿调不过…

1025是说有一些木板，有长度和质量，要求找出递增（两个量都必须满足不小于的条件）的序列数。老题了，按两个关键字排序，然后贪心地加板子把序列弄出来就可以了。正确性可以这样看：首先，这样的贪心每一步可以得出一条长度极大的序列。这是很显然的，如果存在一条起点相同而比贪心得出的序列更长的序列B的话，那么假设B与贪心得出的序列A的第一个分叉点为C。也就是说C之前A与B都相同而C之后首次出现不同。由于贪心规测可以保证起点之后所有可以进入序列的板子都进入了，因此C不会超过起点，而起点相同，因此C不是起点，矛盾。其次，所有的序列可以用一些长度极大的序列的并表示。如果存在某个序列集，满足其中的序列数小于长度极大的序列的总数，那么其中的任何一个序列的长度一定小于相同起点的极大序列，把这些序列加起来，总长度一定小于极大序列的长度和，因此这个序列集一定不包含所有顶点。这就说明了这个贪心的正确性。

其实这个我一开始是没想到的，后来看了别人的才猛然醒悟，这题居然被归类在DP里头，于是我老是往DP方向想，囧。