牛客小白月赛38 C.糟糕的打谱员(DP)
2021/9/25 23:15:21
本文主要是介绍牛客小白月赛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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享