《舰队游戏》题目分析
+~~~~~~~~~~~~~~~~~+ < < < < < < < < <
| +-+ +-+ +-+ +-+ | <+-< <+-< <+-< <+-< <+-< <+-< <+-< <+-< <+-<
| |1| |2| |5| |4| | < < < < < < < < <
| | | | | | | | | |
| | | | | | | | | | 0 0 0 0 5 3 3 2 7
| +-+ +-+ +-+ +-+ | 2 4 1 6 0 0 0 0 0
+~~~~~~~~~~~~~~~~~+
《舰队游戏》的题目描述比较长。不过我们读懂题意之后，可以发现题目要求就是判断给每一个装备栏位部署哪驾飞机。
首先想到就是可以暴力枚举。一共有NM个装备栏，每个装备栏有T驾飞机选择。所以通过O(T^(NM))的枚举算法穷举出所有部署方案，计算出每种方案的制空值和伤害值，从中选择最优的方案即可。这个算法可以得到大约30%的分数。
如果我们仔细分析所有的枚举方案，我们会发现很多情况从一开始就注定不是最优的方案。比如假设我们在搭载量为1和2的武器栏分别部署制空值是5和3的飞机：
+~~~~~~~~~~~~~~~~~+ < < < < < < <
| +-+ +-+ +-+ +-+ | <+-< <+-< <+-< <+-< <+-< <+-< <+-<
| |1| |2| |5| |4| | < < < < < < <
| |5| |3| | | | | |
| |0| |0| | | | | | 0 0 0 0 3 2 7
| +-+ +-+ +-+ +-+ | 2 4 1 6 0 0 0
+~~~~~~~~~~~~~~~~~+
无论后面两个武器栏如何部署，都不会是最优方案。因为我们只需简单交换两架飞机的位置，就能将制空值从11提升到13:
+~~~~~~~~~~~~~~~~~+ < < < < < < <
| +-+ +-+ +-+ +-+ | <+-< <+-< <+-< <+-< <+-< <+-< <+-<
| |1| |2| |5| |4| | < < < < < < <
| |3| |5| | | | | |
| |0| |0| | | | | | 0 0 0 0 3 2 7
| +-+ +-+ +-+ +-+ | 2 4 1 6 0 0 0
+~~~~~~~~~~~~~~~~~+
这给了我们一个提示，如果我们确定了每个武器栏是装备对空还是对舰飞机，那么我们一定是优先把攻击力最高的飞机部署在搭载量最高的武器栏中。（排序不等式，有没有种似曾相识的感觉）
所以我们可以优化我们的枚举算法。首先把飞机分为对空和对舰两类，对两类飞机分别根据攻击力排序，复杂度O(TlogT)。再用O(2^(NM))的算法枚举每个武器栏位是装备对空还是对舰飞机；对于每种情况，由于一定是优先把攻击力最高的飞机部署在搭载量最高的武器栏中，可以在O(NM)的时间内计算出最优的对空值和伤害值。
这样我们总的复杂度就是O(TlogT + 2^(NM)NM)。
本题最后还有一个需要注意的问题是飞机有可能不足。比如我们枚举的方案是有10个武器栏部署对空飞机，但是对空飞机总共只有9驾。这样情况需要特殊判断一下，不再赘述。
