反恐训练营-白红宇

反恐训练营

阅读量：200 次

发布时间：2019-02-28

本文共 1602 字，大约阅读时间需要 5 分钟。

根据上述分析，我们可以使用动态规划的方法来解决这个问题。具体步骤如下：

初始化一个二维数组 f，大小为 (n+1) x (m+1)，其中 n 是子弹和恐怖分子的类型数，m 是序列的长度。

填充边界条件：当 i=0 或 j=0 时，f[i][j] = 0。

遍历每个 i 和 j，计算 f[i][j]：

如果 a[i] == b[j]，则 f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + score[a[i]])。

否则，f[i][j] = max(f[i-1][j], f[i][j-1])。

最终，f[m][n] 就是炜炜能获得的最大分数。

通过这种方法，我们可以高效地计算出最优解。

以下是实现代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      using namespace std;int main() {    int n;    while (cin >> n) {        string a_sub, b_sub;        for (int i = 1; i <= n; ++i) {            a_sub += tolower(cin >> (char&c));            b_sub += tolower(cin >> (char&c));        }        map
       
         score;        for (int i = 1; i <= n; ++i) {            int x;            cin >> x;            score[tolower(a_sub[i-1])] = x;        }        int len_a = a_sub.size();        int len_b = b_sub.size();        vector
        
         
          > dp(len_a + 1, vector
          
           (len_b + 1, 0)); for (int i = 1; i <= len_a; ++i) { for (int j = 1; j <= len_b; ++j) { if (a_sub[i-1] == b_sub[j-1]) { if (i == 1 || j == 1) { dp[i][j] = score[a_sub[i-1]]; } else { dp[i][j] = dp[i-1][j-1] + score[a_sub[i-1]]; } } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } cout << dp[len_a][len_b] << endl; } return 0;}