题解 | #田忌赛马#

思路

• 从分治的角度考虑，齐王当前最快的马应当与田忌的哪匹马比赛

  • 若田忌目前最快的马速度比齐王当前最快的马要慢，从贪心的角度考虑，用田忌最慢的马和齐王的这匹马比赛，将速度更快的马保留到后面，使后面赢的场次尽可能多
    • 证明：假设后面能赢的最多场次为k，假设后面当前速度最慢的马是a，其速度是Va，齐王当前最快的马是b，其速度是Vb，我们用速度为Vc的马c和马b对战(Va < Vc < Vb)，此时也能赢k场，那么后面马a的对手用马b对战也一定能赢，通过有限次的数学归纳，最优解可以转化为贪心解，所以该贪心是正确的
  • 若田忌当前最快的马速度与齐王的当前最快的马相同
    • 若这一场让田忌用速度最慢的马输掉比赛，最好的情况下是当前田忌最快的马让后面比赛的某一场原本输掉的结果变为赢，总收益的增量为-200 + 400 = 200，即有可能让总收益增加，所以这种情况下，平局与失败两种可能都要尝试，在这两种子问题中取最大值
  • 若田忌当前最快的马速度与齐王当前最快的马要快
    • 若让这场比赛平局，则在让后面一场输的比赛替换为赢的比赛的最优情况下收益增量为-200 + 400 = 200，但这种情况不成立，假设邹忌能和齐王平局的马为x，那么x的速度一定大于等于齐王后面的马，也就是说这匹马在后面不可能输掉比赛。这种情况下替换的最大收益可能为-200
    • 若让这场比赛输掉，则在让后面一场输的比赛替换为赢的比赛的最优情况下，收益增量为-400 + 400 = 0
    • 总上，田忌能赢的情况下一定要赢，这样收益一定最大
    • 若邹忌有多匹马可以赢，使用哪匹马赢的结果都是一样的，因为这些马能赢齐王当前最快的马，那么就意味着这些马也一定能赢齐王后面的马，因此无论这一局选用哪匹马，剩下的马在后面也一定会赢，在能赢的马中无论选哪一批，都不会影响后面能赢的最大场数。为了方便做动态规划，这里用当前速度最快的马即可

• 由于上述讨论是基于当前最快的马进行的，所以需要将马的速度按大小顺序排序，这里以从小到大为例

• 综上，齐王最快的马

  • 速度大于田忌最快的马时，田忌出战速度最慢的马
  • 速度等于田忌最快的马时，田忌出战速度最快的马和出战速度最慢的马都要尝试
  • 速度小于田忌最快的马时，田忌出战速度最快的马

• 将上述结果进一步总结，齐王最快的马应当尝试与田忌最快的马和田忌最慢的马进行匹配，取结果最大值即可

• 状态设计

  • dp[i][j]：设len = j - i + 1，该状态表示齐王前len匹马(当前最快的马)与田忌的[i, j]匹马(也是len匹马)比赛获取的最大收益(由于排序，所以第len匹马就是前len匹马中速度最快的)

• 状态转移

  • 为了方便表述，用v[0][k]表示邹忌的第k匹马，用v[1][k]表示齐王的第k匹马，cmp(x, y)函数用于比较大小，x大于y返回1，等于返回0，小于返回-1
  • 由上述讨论可知，齐王的第len匹马(当前最快的马)应当与田忌当前的第i匹马(速度最慢)或第j匹马(速度最快)进行匹配，取结果的最大值，因此公式为dp[i][j] = max(dp[i][j - 1] + 200 * cmp(v[0][j], v[1][len]), dp[i + 1][j] + 200 * cmp(v[0][i], v[1][len]));

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 5010;
int v[2][MAX], n;
int dp[MAX][MAX];

int cmp(int a, int b) {
	if (a == b) return 0;
	return a < b ? -1 : 1;
}

LL solve() {
	for (int i = 0; i < 2; i++) sort(v[i] + 1, v[i] + n + 1);
	
	for (int len = 1; len <= n; len++) {
		for (int i = 1; i + len - 1 <= n; i++) {
			int j = i + len - 1;
			dp[i][j] = max(dp[i][j - 1] + 200 * cmp(v[0][j], v[1][len]), dp[i + 1][j] + 200 * cmp(v[0][i], v[1][len]));
		}
	}
	
	return dp[1][n];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> n;
	
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> v[i][j];
		}
	}
	
	LL ans = solve();
	
	cout << ans;
	
	return 0;
}