$田忌赛马$田忌赛马

题目见链接 .

$最初想法$最初想法

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

$正解部分$正解部分

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

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

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

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

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

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

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

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

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

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

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

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

$实现部分$实现部分

#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\n", Ans);
}

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