自动搬运

查看原文

来自洛谷，原作者为

	LBY1145141919810 been eaten了||想膜拜風神||轻雨何故落||可我是蒟蒻罪人呀……

搬运于2025-08-24 22:23:18，当前版本为作者最后更新于2025-05-09 16:09:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

标签：

LCS

思路：

感觉和 LCS 很像

于是就跟着感觉推了。

设 $dp_{i,j}$ 为野鹅队打了 $i$ 场，老鹰队打了 $j$ 场，两队之间的同德城比得分之和的最大值。

于是就容易发现，这个问题和 LCS 经典模型很像。

我们可以发现，如果一场是同德城比，当且仅当以下两种情况的一种：

• $c_{0,i}= W$ 且 $c_{1,j}= L$ 且 $a_{0,i} > a_{1,j}$

• $c_{0,i}= L$ 且 $c_{1,j}= W$ 且 $a_{0,i} < a_{1,j}$

其中 $c_{0/1,x}$ 表示野鹅/老鹰队的第 $x$ 场赢（W）/ 输（L）

而 $a_{0/1,x}$ 表示野鹅/老鹰队的第 $x$ 场的得分情况。

很显然，我们联系 LCS ，发现 LCS 的状态转移方程是：

$$dp_{i,j}= \begin{cases} \max\{dp_{i,j-1},dp_{i-1,j}\} & \forall (i,j)\\ \max\{dp_{i,j},dp_{i-1,j-1}+1\} & a_i=b_j (string a,b) \end{cases} $$

于是我们这道题的状态转移方程同理：

$$dp_{i,j}= \begin{cases} \max\{dp_{i,j-1},dp_{i-1,j}\} & \forall (i,j)\\ \max\{dp_{i,j},dp_{i-1,j-1}+a_{0,i}+a_{1,j}\} & Win \end{cases} $$

那么这道题就做完了，因为初值为 $0$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1033;
int dp[N][N];
int n;
char c[2][N];
int a[2][N];
int main(){
	cin>>n;
	for(int k=0;k<2;k++){
		for(int i=1;i<=n;i++)cin>>c[k][i];
		for(int i=1;i<=n;i++)cin>>a[k][i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(c[0][i]=='W'&&c[1][j]=='L'&&a[0][i]>a[1][j]){
				dp[i][j]=max(dp[i-1][j-1]+a[0][i]+a[1][j],dp[i][j]);
			}
			if(c[0][i]=='L'&&c[1][j]=='W'&&a[0][i]<a[1][j]){
				dp[i][j]=max(dp[i-1][j-1]+a[0][i]+a[1][j],dp[i][j]);
			}
		}
	}
	cout<<dp[n][n];
	return 0;
}

总结：

需要熟练掌握 LCS 的模型，并熟悉它的变种。

十年 OI 一场空，不开 ll……不会死。。。