题解：P6713 [CCO 2018] Geese vs. Hawks

· · 题解

标签：

LCS

思路：

感觉和 LCS 很像

于是就跟着感觉推了。

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

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

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

其中 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……不会死。。。