田忌赛马 [贪心(完成) / 动态规划(待填坑)]

$田忌赛马$

题目见链接 .

---

$color{blue}{最初想法}$

设 $F[i, j]$ 表示前 $i$ 场比赛, 使用的马属于前 $j$ 匹马的最大收获,
则 $F[i, j] = max(F[i, j-1], F[i-1, j-1]+cost_j)$,
但是这样 $dp$ 不能覆盖所有情况, 决策时只考虑了 选择前 $j$ 匹马 .

---

$color{red}{正解部分}$

• 当田忌最快的马 快于 齐王最快的马, 直接赢 .

$Q:$ 为什么不使用刚好快于齐王最快的马?
$A:$ 因为若两匹马同时大于齐王最快的马时, 这两匹马都大于齐王的任何一匹马, 使用哪个没有区别 .

• 当田忌最快的马 慢于 王最快的马, 拿最慢的马抵掉 王 最快的马 .
• 当田忌最快的马 等于 王最快的马, 有两个选择,
  1. 使用最慢的马输掉 .
  2. 使用最快的马平局 .

---

$Q:$ 第三个分支如何选择 ?
$A:$ 看情况, 具体来说 $↓$,

• 若最慢的马可以赢掉王的其中一个马,

  1. 选择序号 $2$, 最慢的马赢可以得到 $200$ 金币, 最快的马平局 ,
     总得失: 得到 $200$ 金币 .
  2. 选择序号 $1$, 最慢的马输掉得到 $-200$ 金币, 那个最快的马到后面会赢, 可能平局,
     就算最快的马赢了, 得到 $200$ 金币,
     总得失: 得到 $0$ 金币 .

  综上所述, 若最慢的马可以赢掉王的其中一匹马, 就拿最慢的马去赢, 最快的马去平 .

• 若最慢的马不可以赢掉王的任何一个马,

  1. 选择序号 $1$, 得到 $-200$, 最快马可能会赢, 也可能平局,
     总得失: $[-200, 0]$
  2. 选择序号 $2$, 得到 $0$, 最慢的那匹马一定会输, 得到 $-200$,
     总得失: $-200$.

  选择序号 $1$, 还有赚钱的希望,
  综上所述, 若最慢的马不可以赢掉王的任何一个马, 就拿最慢的马去浪费掉王的最快马 .

由于每场比赛田忌随意择马, 所以为了更方便处理, 先将齐王的马从大到小排序, 对答案没有影响 .

---

$dp$ 的方法就待填坑吧…
_咕咕咕

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register

int N;
int A[2005];
int B[2005];

void Work(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &B[i]);
        std::sort(A+1, A+N+1), std::sort(B+1, B+N+1);
        int la = 1, ra = N, lb = 1, rb = N;
        int Ans = 0;
        while(la <= ra){
                if(A[ra] > B[rb]) ra --, rb --, Ans += 200;
                else if(A[ra] < B[rb]) la ++, rb --, Ans -= 200;
                else if(A[la] > B[lb]) la ++, lb ++, Ans += 200; 
                else{
                        if(A[la] < B[rb]) Ans -= 200; // !!!
                        la ++, rb --;
                }
        }
        printf("%d
", Ans);
}

int main(){
        int T = 1;
//        scanf("%d", &T);
        while(T --) Work();
        return 0;
}