题目描述

题目:田忌赛马的故事，田忌每次输一局要付200元，赢一局获得200元，平局获得0元
问，田忌和齐王都有n匹马的情况下，最多可以获得多少元

看了一圈题解区，好像没有区间dp的题解，虽然比较复杂，但是还是能ac的…

(区间dp) $O(n^2)$

步骤
- 贪心
- 区间dp

贪心

由于田忌赛马的故事背景，我们很快就能够想到合理的贪心策略，上等马对中等马，下等马对上等马，所以可以将齐王和田忌的马都按照从大到小降序排序
那么排序之后，对于田忌当前最大的马，如果比齐王最大的马还快，就用。如果田忌当前最大的马，如果比齐王最大的马还慢，就用田忌最小的马。

证明： 当前都是按照降序排序，田忌目前的马如果比齐王最大的马还快，那么田忌max马能够满足比齐王所有的马都快，那贪心的想肯定是和齐王最快的匹配。这种贪心决策不会存在影响后面的决策，具有可拓展性。如果田忌当前最大的马，如果比齐王最大的马慢，都是输，倒不如选用田忌最小的马，因为最小的马能匹配的对象，它前面的马都能匹配上，不会影响决策。

贪心决策：

• 当前田忌MAX>齐王MAX,选用田忌的MAX
• 当前田忌MAX<齐王MAX,选用田忌的MIN

这个贪心决策处理田忌赛马使田忌赢场次最多的问题是正确的，但是本题是求最多的银元数，单一的贪心决策是错误的，因为无法处理平局的情况(样例：田忌2 3 齐王1 3 )，因为无论平局时选择MIN或者MAX，都不一定能够确保最优解

区间dp

由于我们的贪心决策一定只会从MIN，MAX两个当中选一个出来，遇到平局就可以枚举一下选哪个更好，枚举的时间复杂度是指数级的，这题就不妨用dp来替代枚举，因为只会选择两端的马，就类似于一个不断缩小的区间，所以用区间dp
我们先固定齐王的马数组，从大到小排序后，然后田忌每轮都选择一个MAX，MIN和齐王比较，共计n轮（正难则反）

递推关系：本题在做出一个决策时，必须先知道选择这个决策之后会发生什么(如果不知道的话就无法递推)，所以可以逆向递推，就是先枚举出后k轮的情况，从后往前递推(或者记忆化搜索)

原问题：比较完n轮后，用田忌[1,n]区间中所有马比较获得的最大银元数

子问题：比较完后k轮，用田忌[i,j]区间中所有马比较获得的最大银元数

状态表示：dp[k][i][j]:比较完后k轮，用田忌[i,j]区间中所有马比较获得的所有集合的最大值

子集划分/状态计算：对于一个区间[i,j]来说，根据  划分依据：最后一次做出的决策  ，可以划分为不重不漏的两个子集

• 第k轮时，选择i去比较               dp[k][i][j]=max(dp[k-1][i+1][j]+cmp(a[i],b[k]))
• 第k轮时，选择j去比较               dp[k][i][j]=max(dp[k-1][i][j-1]+cmp(a[j],b[k]))

初始化：由于可能全输，全部初始化为负无穷

边界：由于逆向推理，dp[i][i]=cmp(a[i],b[n])

由于逆向推理，田忌马数组按照从大到小排序，齐王马数组按照从小到大排序
因为表示后k轮，只有j-i+1=len==k时，才可以发生递推([i,j]区间所有元素都要被使用到)，所以k可以省略，就优化到了n^2

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
int a[N];
int b[N];
int dp[N][N];
int  cmp(int a, int b)
{
    if (a > b) return 200;
    if (a == b) return 0;
    return -200;
}
void solve(int n)
{
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    for (int i = 1;i <= n;i++)
        cin >> b[i];
    sort(a + 1, a + 1 + n, [](const int& a1, const int& b1) {return a1 > b1;});
    sort(b + 1, b + 1 + n, [](const int& a1, const int& b1) {return a1 < b1;});
    int res = -0x3f3f3f;
    memset(dp, -0x3f, sizeof dp);


        for (int len = 1;len <= n;len++)
            for (int i = 1;i + len - 1 <= n;i++)
            {
                int j = i + len - 1;
                int k = len;
                if (len == 1)
                    dp[i][j] = cmp(a[i], b[k]);
                else
                    dp[i][j] = max(dp[i + 1][j] + cmp(a[i], b[k]), dp[i][j - 1] + cmp(a[j], b[k]));
            }
    res = dp[1][n];
    cout << res << endl;
}
int main()
{
    int n;
    while (cin >> n, n)
        solve(n);
    return 0;
}