题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1052
题目大意：
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马（N≤2000），每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？
算法分析：
这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马A和齐王的B之间，如果田忌的马胜，则连一条权为200的边；如果平局，则连一条权为0的边；如果输，则连一条权为－200的边。
然而我们知道，二分图的最佳匹配算法的复杂度很高，无法满足N＝2000的要求。
我们不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权”，他总是根据齐王所出的马来分配自己的马，所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设，我们归纳出如下贪心策略：
Ø 1、如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马，那么应该用最差的一匹马去输给齐王最强的马。
Ø 2、如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马，那就用这匹马去赢齐王剩下的最强的马。
Ø 3、如果田忌剩下的马中最强的马和齐王剩下的最强的马打平的话，可以选择打平或者用最差的马输掉比赛。
第一个贪心策略的证明：
此时田忌的所有马都赢不了齐王的马，所以无论用最慢马去输还是用最快的马去输都同样是输，而处于贪心的思想，我们应该保留相比之下更强的马，因此用最慢的马去输一定不会比用别的马去输来得劣，所以这是最优策略。
证毕。
第二个贪心策略的证明：
假设现在齐王剩下的最强的马是A，田忌剩下的最强的马是B，如果存在一种更优的比赛策略，让B的对手不是A，而使得田忌赢更多的钱的话，那么设此时A的对手是b，B的对手是a：
1、 若b>A，则有B>a，b>A。这个结果和B>A，b>a是相同的。
2、 若a<b≤A，则有B>a，b≤A。这个结果不如B>A，b>a来得优秀。
3、 若b≤a≤A，则有B>a，b≤A。这个结果和B>A，b≤a是相同的。
由此可知，交换各自对手后，一定不会使得结果变劣，那么假设是不成立的。
证毕。
第三个贪心策略的证明：
因为田忌最快的马也只是和齐王的马打平，那么田忌只能选择平或输，选择平的话，当然只能用最快的马去平了；选择输的话当时是用最慢的马去输来得值得，这和第一个贪心策略的思路是一样的。
证毕。
我们发现，第三个贪心策略出现了一个分支：打平或输掉。如果穷举所有的情况，算法的复杂度将比求二分图最佳匹配还要高；如果一概而论的选择让最强的马去打平比赛或者是让最差的马去输掉比赛，则存在反例：
ü 光是打平的话，如果齐王马的速度分别是1 2 3，田忌马的速度也是1 2 3，每次选择打平的话，田忌一分钱也得不到，而如果选择先用速度为1的马输给速度为3的马的话，可以赢得200两黄金。
ü 光是输掉的话，如果齐王马的速度分别是1 3，田忌马的速度分别是2 3，田忌一胜一负，仍然一分钱也拿不到。而如果先用速度为3的马去打平的话，可以赢得200两黄金。
虽然因为第三个贪心出现了分支，我们不能直接的按照这种方法来设计出一个完全贪心的方法，但是通过上述的三种贪心策略，我们可以发现，如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。有了这个信息之后，动态规划的模型也就出来了！
设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。
状态转移方程如下：
其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为200，输为－200，平为0。
本题小结：
虽然本题存在直接贪心的方法，不过它可以作为一个例子告诉大家，合理的运用贪心策略，分析出问题的一些本质之后，一些看似不能用动态规划做的题目便可以巧妙的确立出状态，继而可以用动态规划来求解。
-----------------2006 - 黄劲松《贪婪的动态规划》
贪心：
#include <cstdio>
#include <algorithm>
#include <functional>//less<int>(), greater<int>();
using namespace std;
int a[1005], b[1005];
int n;
int main()
{
int ans, i, f1, f2, r1, r2;
while (scanf("%d", &n), n) {
for (i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n, greater<int>());
for (i = 0; i < n; i++) scanf("%d", &b[i]);
sort(b, b + n, greater<int>());
f1 = f2 = 0;
r1 = r2 = n - 1;
ans = 0;
while (f1 <= r1) {
if (a[f1] > b[f2]) {
f1++;
f2++;
ans += 200;
} else if (a[f1] < b[f2]) {
f2++;
r1--;
ans -= 200;
} else {//当前两人的最快的马的速度相等
if (a[r1] > b[r2]) { //如果田忌的最慢的马能赢国王的最慢的马，则先比较最慢的马。
r1--;
r2--;
ans += 200;
} else {//田忌的最慢的马不能赢国王的最慢的马。则用最慢的马跟国王的最快的马比。
if (a[r1] < b[f2]) {
ans -= 200;
}
r1--;
f2++;
}
}
}
printf("%d\n", ans);
}
return 0;
}
动态规划：