C/C++教程

牛客小白月赛38 C.糟糕的打谱员(DP)

本文主要是介绍牛客小白月赛38 C.糟糕的打谱员(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 题目:糟糕的打谱员

  • 题意:给出一个长度为n(\(3 \leq n \leq 10^5\))的谱子,第\(i\)个谱子记录有两个数:\(c_i\)代表下这步棋的人为0或1(黑方白方),\(a_i\)代表此步棋下在某个地方的编号,此时需要计算出一个最长子序列的长度,满足相邻的两个数\(c_i \neq c_{i-1} \& a_i \neq a_{i - 1}\)。

  • 解析:首先类似于最长上升子序列,会相当O(n^2)的DP算法,但是此题可以用空间进行优化,通过一个二维数组\(pos_{c,j}(0 \leq c \leq 1,1 \leq j \leq 10)\) 表示在第i个数之前作为黑方或白方最后一步在编号\(j\)可得到的最长序列长度的位置(原谱子中的位置),通过\(c \oplus 1\)可以将黑方变成黑方。

    • 状态转移方程: \(f[i] = max(f[i], f[pos[c[i]\oplus1][j]] + 1)\) (与第i步棋手相反棋手在编号\(j\)得到的最长序列 + 上第i步棋(其实就是1))。
    • ps:若下的棋以编号j结尾的c[i]玩家最长序列值大于之前的序列长度值,则位置信息需要进行更新。
  • 代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int N  = 1e5 + 5;
    int T;
    int n;
    int c[N], a[N], pos[5][15];
    int f[N]; //到第i个位置可得到的最长的合法行棋子序列
    
    int main()
    {
        cin >> T;
        while(T --)
        {
            cin >> n;
            memset(f, 0, sizeof f);
            int res = 0;
            for(int i = 1; i <= n; i++)
                cin >> c[i] >> a[i];
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= 10; j++)
                {
                    if(a[i] == j) continue; //相邻两个位置的编号不能相同
                    f[i] = max(f[i], f[pos[c[i]^1][j]] + 1); //相邻两个位置玩家不能相同
                }
                if(f[i] > f[pos[c[i]][a[i]]]) pos[c[i]][a[i]] = i; //若以j结尾的c[i]玩家最长序列值改变, 则更新位置信息
                res = max(res, f[i]);
            }
            cout << res << endl;
        }
        return 0;
    }
    
    
这篇关于牛客小白月赛38 C.糟糕的打谱员(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!