这题一开始我想的是n2，然后发现a[i]的最大值为10，与之前暴力dp相结合。
设置一个桶为t[i][j]代表下在i处的j颜色所代表的最大步数。
那么dp[i]=max(dp[i],t[a[i].second][!a[i].first])
#include<bits/s
展开全文
本题要求从一个记录序列中找出最长的子序列，满足相邻两步玩家交替且劫争编号不同。由于劫争编号范围很小（1~10），可以采用动态规划，按顺序扫描每一步，维护以每种（玩家，劫争）组合结尾的最长子序列长度。对于当前步 (c, a)，它可以接在之前任意一个与 c 不同且劫争不等于 a 的状态之后，因此只需从另
展开全文
因为题目规定
任意相邻的两步，玩家不同（一黑一白）；
任意相邻的两步，不能下在同一个劫争处。
我们只需要对每个操作枚举一下a，状态转移方程:dp[i]=max(dp[i],dp[pre[j][k]]+1);a，状态转移方程:dp[i] = max(dp[i],dp[pre[j][k]] +
展开全文
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_A = 11;
int main() {
ios::sync_wi
展开全文
线段树是对的孩子们，因为普通dp的话只能想出来O(n2)的做法只好用线段树O(nlogn)的方法过去了。开两个线段树，一个是0下棋的时候，另一个是1下棋的时候，每次都在对方的范围里面查找不是以ai结尾的最大的合法长度就好了最后把两边最大的长度比一下就好了
#include<bits/stdc+
展开全文
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
