首页 > 其他分享 >题解 P11233【[CSP-S 2024] 染色】

题解 P11233【[CSP-S 2024] 染色】

时间:2024-11-04 18:58:11浏览次数:3  
标签:10 return leq P11233 题解 2024 int buc define

题目描述

给定一个长度为 \(n\) 的正整数数组 \(A\),其中所有数从左至右排成一排。

你需要将 \(A\) 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:

设 \(C\) 为长度为 \(n\) 的整数数组,对于 \(A\) 中的每个数 \(A_i\)(\(1 \leq i \leq n\)):

  • 如果 \(A_i\) 左侧没有与其同色的数,则令 \(C_i = 0\)。
  • 否则,记其左侧与其最靠近的同色数为 \(A_j\),若 \(A_i = A_j\),则令 \(C_i = A_i\),否则令 \(C_i = 0\)。

你的最终得分为 \(C\) 中所有整数的和,即 \(\sum \limits_{i=1}^n C_i\)。你需要最大化最终得分,请求出最终得分的最大值。

对于所有测试数据,保证:\(1\leq T\leq 10\),\(2\leq n\leq 2\times 10^5\),\(1\leq A_i\leq 10^6\)。

solution

两种颜色是没有区别的。\(f_{i, j}\) 表示一种颜色最后一个选的是 \(i\),另一种颜色最后一个选的是 \(j\),要求 \(j<i\)。转移枚举 \(i+1\) 与 \(i, j\) 中的哪一个同色。转移到 \(f_{i+1, j}\) 和 \(f_{i+1, i}\) 中的一个。仔细考虑也就是

\[f_{i, j}+[a_i=a_{i+1}]a_{i+1}\to f_{i+1, j} \]

\[f_{i, j}+[a_j=a_{i+1}]a_{i+1}\to f_{i+1, i} \]

将 \(i\) 这一维去掉,第一种转移是全局加(直接维护标记),第二种转移是单点修改(事实上甚至是 push_back,不会影响其它已计算的值),需要支持查询全局最大值和 \(a_j=a_{i+1}\) 的 \(f_j\) 的最大值,前者用一个变量维护,后者开一个桶维护。我写的复杂度是 \(O(T(n+V))\)。

code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define endl "\n"
#endif
using LL = long long;
template <class T> T& cmax(T& x, const T& y) { return x = max(x, y); }
template <class T> T& cmin(T& x, const T& y) { return x = min(x, y); }
int n, a[200010];
LL buc[1000010];
int mian() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  memset(buc, ~0x3f, sizeof buc);
  LL tag = 0, mx = 0;
  buc[0] = 0;
  for (int i = 2; i <= n; i++) {
    LL val = max(mx, buc[a[i]] + tag + a[i]);
    if (a[i] == a[i - 1]) tag += a[i], mx += a[i];
    cmax(mx, val), cmax(buc[a[i - 1]], val - tag);
  }
  cout << mx << endl;
  return 0;
}
int main() {
#ifndef LOCAL
#ifdef NF
  freopen("color.in", "r", stdin);
  freopen("color.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  int t;
  cin >> t;
  while (t--) mian();
  return 0;
}

标签:10,return,leq,P11233,题解,2024,int,buc,define
From: https://www.cnblogs.com/caijianhong/p/18526012/solution-P11233

相关文章

  • 个人提升计划-2024
    今天的目标,就是定一个目标。打开博客,重新写学习计划。打开后台,一眼看到3年前定的学习计划,不禁有点好笑。3年前写的学习计划,终究是没有完成。时间如白驹过隙,转瞬即逝。3年就这么悄咪咪地过去了。收起诸多无用的感慨,制定好短期的个人提升计划吧。这个计划,我认为还是要先定好方向......
  • 牛客周赛 Round 66 题解
    牛客周赛Round66题解牛客周赛Round66A-小苯吃糖果_牛客周赛Round66#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;inta[5];voidsolve(){ for(inti=1;i<=3;i++)cin>>a[i]; sort(a+1,a+4); intans=max(a[1]+a[2],a[3]); cout<......
  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • 【网络云计算】2024第44周周考-解题思路
    文章目录1、网络类1.1、【网络类】arp的实操过程和总结1.2、IP地址的分类及地址范围1.3、网工/云计算SA必备网络故障排查思路和指令,不同维度分析,思路对应指令1.4、OSI和TCP模型,写成两列,并分别写出每层模型的含义2、架构类2.1、如何部署Tomcat,出错无法启动Tomcat实例,如何......
  • 【网络云计算】2024第45周小测第1次-Shell编程类
    文章目录1.1、CentOSStream9系统初始化的流程和步骤,步骤和指令对应,编写Shell脚本,并添加注释1.2、写出你所知道的所有的Shell编程的基本语法【网络云计算】2024第45周小测第1次-Shell编程类1.1、CentOSStream9系统初始化的流程和步骤,步骤和指令对应,编写Shell脚本......
  • NeurIPS 2024 | 真实世界复杂任务,全新基准GTA助力大模型工具调用能力评测
     点击访问我的技术博客https://tmqcjr.com/利用语言模型调用工具,是实现通用目标智能体(general-purposeagents)的重要途径,对语言模型的工具调用能力提出了挑战。然而,现有的工具评测和真实世界场景存在很大差距,局限性主要体现在以下几个方面:评估问题通常是AI生成的,形式固......
  • 2024-11-04_Mon_14:10 - 帕金森定律:支出永远与收入成正比
    2024-11-04_Mon_14:10-帕金森定律:支出永远与收入成正比​​【网图,侵删】‍财富,不断增加净值增加净值的途径增加收入增加存款增加投资获利减低消费支出永远与收入成正比穷人认为“存款,是有钱人的做的”,“我现在没钱,等我有钱了,在考虑存款”支出永远与收入成......