http://acm.hdu.edu.cn/showproblem.php?pid=1052
题目内容就是田忌赛马，解决思路就是贪心，关键是要怎么贪，。
我在看完题目后想到一种方法，就是田忌速度最大的马开始，尽量和速度最接近的马来比，这样结果无非就是平局或获胜，无法匹配的马就当输了。
本以为这样可以减少马“性能”上的浪费，就能得到最优解。但有组数据就能当反例：
3
92 83 70
92 91 60
按照我的算法，92和92 配对，83就只能和60配了。最优的是92和91配，83和60配。
我的算法关键就错在对于平局是可以有两种方法的，但我只处理了一种。
下面来正确的：
1.当田忌最慢的马比齐王最慢的马快，赢一场先。
如果不赢，最慢的马可能就比不上KING第二慢的马；符合“性能”上的节约。
2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。
既然一定会输，何不“带”死对方最厉害的？
3.如果一样快：
1.当田忌最快的马比齐王最快的马快时，赢一场先。符合“性能”上的节约。
2.当田忌最慢的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场。
最难理解的就是这条了！关键这里包括最快的马平局的情况，为什么要故意输一场？
拿最慢的马带死King最快的马，那么自己最快的马肯定能赢king的下一匹马，
自己第二慢的马肯定能赢King最慢的马，补回来了！剩下的好理解了。
3.当田忌最慢的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比。平局。
其实也可以先从两人最快的马开始考虑，只要当前的选肯定是最优的就行了。
AC代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int cmp(const void *a,const void *b) 5 { 6 return *(int*)a-*(int*)b; 7 } 8 9 int a[1002],b[1002]; 10 inline void read(int *p,int n) 11 { 12 for (int i=0; i<n; ++i) scanf("%d",p+i); 13 } 14 int main() 15 { 16 int n; 17 while (~scanf("%d",&n) && n) 18 { 19 read(a,n); 20 read(b,n); 21 qsort(a,n,sizeof(a[0]),cmp); 22 qsort(b,n,sizeof(b[0]),cmp); 23 int ans=0; 24 int i=0,j=0,in=n-1,jn=n-1; 25 while(i<=in) 26 { 27 if (a[i]>b[j]) {++ans;++i;++j;continue;} 28 if (a[i]<b[j]) {--ans;++i;--jn;continue;} 29 if (a[in]>b[jn]) {++ans;--in;--jn;continue;} 30 if (a[i]<b[jn]) --ans; 31 ++i;--jn; 32 } 33 printf("%d\n",ans*200); 34 } 35 }
当然这题也有DP的解法：
用f[i][j]表示齐王出第i匹马，田忌在前面(速度慢的马)选了j匹马（后面选了i-j匹马）的最优值
由此可见，当前齐王出得马是i号马，田忌要么出j号马，要么出从后数的第i-j匹马，总共有n匹马的话，
从后数第i-j匹马就是从前数的第n-(i-j)+1号马，所以说当前田 忌要么拿j马和齐王i马比要么拿n-(i-j)+1号马和齐王比。
f[i][j]的值就在这两种决策中选个最优