1045 Favorite Color Stripe-白红宇

1045 Favorite Color Stripe

阅读量：430 次

发布时间：2019-03-06

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

为了解决这个问题，我们需要找到给定颜色条带中最长的子串，该子串与Eva的最爱颜色序列相同。我们可以使用动态规划来解决这个问题。

方法思路

问题分析：我们需要在给定的颜色条带中找到最长的子串，这个子串的颜色顺序必须与Eva的最爱颜色序列一致。我们可以使用动态规划来记录每个位置的最长匹配长度。

动态规划定义：定义 dp[i][j] 为Eva的最爱颜色序列的前 i 个颜色在颜色条带的前 j 个颜色中的最长子串长度。

状态转移：

如果当前Eva的最爱颜色与当前颜色条带的颜色相等，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1。

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

初始化：边界条件是 dp[0][j] 和 dp[i][0] 都为0，因为没有颜色匹配的情况下，长度为0。

解决代码

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int n, m, l;
    cin >> n >> m >> l;
    
    vector
     
       favorited(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> favorited[i];
    }
    
    vector
      
        stripe(l + 1);
    for (int i = 1; i <= l; ++i) {
        cin >> stripe[i];
    }
    
    vector
       
        
         > dp(m + 1, vector
         
          (l + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= l; ++j) { if (favorited[i] == stripe[j]) { int option1 = dp[i-1][j]; int option2 = dp[i][j-1]; dp[i][j] = max(option1, option2) + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } cout << dp[m][l] << endl; return 0; }

代码解释

读取输入：首先读取输入数据，包括颜色数量、Eva的最爱颜色数量、条带颜色数量以及具体的颜色值。

初始化动态规划表：创建一个二维数组 dp，用于存储每个状态的最长子串长度。

填充动态规划表：遍历每个可能的位置，更新 dp 表中的值，根据当前颜色是否匹配Eva的最爱颜色来决定状态转移。

输出结果：最终输出 dp[m][l]，即Eva的最爱颜色序列在颜色条带中的最长子串长度。

这种方法通过动态规划有效地解决了问题，确保了在合理的时间复杂度内找到最优解。

转载地址：http://lstuz.baihongyu.com/

你可能感兴趣的文章