csp2024T3

题目大意:对于每个数而言,可以将其染成红或蓝,对于每一个数,定义其贡献为ai,当且仅当这个数最近的同色数与其相等,否则其贡献为0,求最大贡献和。

思路:考虑dp

1.考场20多分钟想的奇怪东西:

定义f[n][0/1]表示第i为的颜色为蓝或红,则有转移:f[i][0]=f[j][0]+(a[i]==a[j])*a[i]+calc(j+1,i-1,1)

f[i][1]=f[j][1]+(a[i]==a[j])*a[i]+calc(j+1,i-1,0)

问题出在calc中,当时想的是sum=\sum_{st}^{ed}f[i][cl]就是他的值。但其实拿那个样例比对一下,就能发现sum=f[st][cl]+sum_{st+1}^{ed}(a[i]==a[i-1])*a[i],对于最左边的数,它的贡献是f[st][cl],其他点就是把相邻两个数的值相等的贡献加起来。注意到如果相邻两个相同数被染成同样的颜色,那么应该是f[st-1][cl](一定要拿特殊数据测一测,否则只有5pts)。

2.O(n^2)呼之欲出,维护前缀和q[i]表示前i位的calc值,那么calc(j+1,i-1)=q[i-1]-q[j+1+1-1]=q[i-1]-q[j+1]

q[i]=a[i]*(a[i]==a[i-1])

q[i]+=q[i-1]

#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int f[N],n,a[N],ans;int calc(int st,int ed){int ans=f[st];if(st>ed&&st-1>=1)  return f[st-1];if(st==ed)  return f[st];for(int i=st+1;i<=ed;i++)  ans+=(a[i]==a[i-1])*a[i]; return ans;
}
void solve(){memset(f,0,sizeof f);cin>>n;for(int i=1;i<=n;i++)  cin>>a[i];for(int i=2;i<=n;i++){f[i]=f[i-1];int sum=0;for(int j=i-1;j>=1;j--){//if(a[i]!=a[j])  continue;int st=j+1,ed=i-1;//st+1 - edif(st>ed&&st-1>=1)  f[i]=max(f[i],(a[i]==a[j])*a[i]+f[st-1]);else if(st==ed)  f[i]=max(f[i],(a[i]==a[j])*a[i]+f[st]);else if(st<ed){sum+=(a[j+2]==a[j+1])*a[j+1];f[i]=max(f[i],(a[i]==a[j])*a[i]+sum+f[st]);} //f[i]=max(f[i],(a[i]==a[j])*a[i]+calc(j+1,i-1));}}cout<<f[n]<<endl;
}
int main(){int T;cin>>T;while(T--)  solve();return 0;
}

考虑优化:很明显只有相等的值才能造成贡献

策略1.两位相邻,f[i]=max(f[i],(a[i]==a[i-1])*a[i]+f[i-1]);

策略2.两位之间差一位,f[i]=max(f[i],(a[i]==a[i-2])*a[i]+f[i-1]);

策略3.两位之间的格子超过两位,f[i]=max(f[i],a[i]+q[i-1]-q[t+1]+f[t+1]);

其中t表示其中与其相同值的格子的位置。

直接分类是接近O(n^2),考虑-q[t+1]+f[t+1]的单调性,可以知道这是单调递增的,每次以上次最后点为起点,t>i-3是为下一个点的起点和这个点的终点即可。

复杂度O(n),当然没看出单调性也可以套个线段树维护后面那个东西,本题不卡常。

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 1e6 + 10;int f[N],n,a[N],ans,q[N],mx,g[N],maxn,lst[N];
vector<int> v[N];
void solve(){memset(f,0,sizeof f);memset(q,0,sizeof q);maxn=0;memset(g,0,sizeof g);memset(lst,0,sizeof lst); cin>>n;for(int i=1;i<=n;i++){cin>>a[i];maxn=max(maxn,a[i]);if(a[i]==a[i-1])  q[i]=a[i];q[i]+=q[i-1];v[a[i]].push_back(i);}  for(int i=2;i<=n;i++){f[i]=f[i-1];int sum=0;f[i]=max(f[i],(a[i]==a[i-1])*a[i]+f[i-1]);if(i>2)  f[i]=max(f[i],(a[i]==a[i-2])*a[i]+f[i-1]);for(int j=lst[a[i]];j<v[a[i]].size();j++){int t=v[a[i]][j];if(t>i-3){lst[a[i]]=j;break;}  f[i]=max(f[i],a[i]+q[i-1]-q[t+1]+f[t+1]);}}cout<<f[n]<<endl;for(int i=1;i<=maxn;i++)  v[i].clear();
}
signed main(){int T;cin>>T;while(T--)  solve();return 0;
}

summary:自己的t2很蒙,搞到t3只有1个小时多一点,实际想这一题只有30-40分钟,没有自己仔细调一调,导致暴力dp都没有写出来。希望noip能自己写出一个正解dp出来

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464665.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

十六届蓝桥杯嵌入式资料 看这个就够了(附CSDN开源程序)

蓝桥杯嵌入式终极模板&#xff0c;简单配置&#xff0c;功能全面 一小时玩转蓝桥杯嵌入式开发版 除按键和 LED 其余模块都来自官方选手资料包 代码简洁工整&#xff0c;参数&#xff0c;函数体分模块&#xff0c;有非常详细的注释&#xff0c;初始化由 cubemx 生成 &#xff08…

【测试工具】Fastbot 客户端稳定性测试

背景 做这个主要为了发版之前提前发现崩溃&#xff0c;风险前置。适合客户端很重的业务。 优点&#xff1a;你不改动也能用&#xff0c; 维护成本不高。 缺点&#xff1a;容易进入H5页面无法返回&#xff0c;效果有限。 备注&#xff1a;我这边接手别人维护&#xff0c;公司…

苍穹外卖Bug集合

初始化后端项目运行出现以下问题 以上报错是因为maven和jdk版本不符合&#xff0c;需要将jdk改成17&#xff0c;mavne改成3.9.9

中国雕塑、

孙溟㠭浅析“印章” 印章又称“图章”&#xff0c;玺印起源商代&#xff0c;至少在春秋战国时已出现&#xff0c;因战国时代已普遍使用。 商玺 古玺是先秦印章的通称&#xff0c;秦始皇统一六国之后&#xff0c;皇帝用印称“璽&#xff08;玺&#xff09;”&…

Android App 技能在DuerOS的调试方法

温故知新&#xff0c;我们先回顾一下DuerOS的技能分类。根据不同的视角可以对DuerOS 目前支持的技能类型进行不同的分类&#xff0c;例如&#xff0c;从用户与技能的语音交互方式来看&#xff0c; 可以将技能分为这四种技能类型: L1技能&#xff1a;只支持语音的打开和关闭L2技…

Ghidra无头模式(自动化批处理执行重复性任务)

Ghidra无头模式&#xff08;自动化批处理执行重复性任务&#xff09; 与Ghidra GUI探索单个项目中的单个文件不同&#xff0c;Ghidra headless analyzer&#xff08;Ghidra无头分析器&#xff09;更加适合批处理和用脚本控制Ghidra。 &#xff08;一&#xff09;启动analyzeHea…

ES海量数据插入如何优化性能?

2024年10月NJSD技术盛典暨第十届NJSD软件开发者大会、第八届IAS互联网架构大会在南京召开。百度文心快码总经理臧志分享了《AI原生研发新范式的实践与思考》&#xff0c;探讨了大模型赋能下的研发变革及如何在公司和行业中落地&#xff0c;AI原生研发新范式的内涵和推动经验。 …

el-date-picker日期选择器动态设置日期

需求&#xff1a;选择开始时间&#xff0c;或者在开始时间已存在的情况下&#xff1b;结束时间下拉日期选择框展示从开始日期展示&#xff1b;而不是当前日期&#xff0c;并且结束时间下拉框日期要禁用开始时间之前的日期。 <el-form-item label"开始时间" prop&q…

web实操2——idea创建普通web项目

创建项目 就是普通的java项目&#xff0c;项目右键add framework support&#xff08;添加框架支持&#xff09;,然后点击Web Application&#xff08;web应用程序&#xff09;&#xff0c;然后点击OK。即可。 文件下就会多一个web文件夹&#xff0c;里面是WEB-INF文件夹&…

ES跟Kafka集成

配合流程 1. Kafka作为分布式流处理平台&#xff0c;能够实时收集和处理不同数据源的数据流&#xff1b; 2. 通过Kafka Connect或者Logstash等中间件&#xff0c;可以将Kafka中的数据流实时推送到Elasticsearch中&#xff1b; 3. Elasticsearch接收到数据后&#xff0c;会根据…

RT-Thread操作系统(2)

RT-Thread操作系统&#xff08;2&#xff09; 目录 RT-Thread操作系统&#xff08;2&#xff09; 设备驱动 IO设备模型框架 PIN设备&#xff08;控制LED灯&#xff09; 软件包开发 DHT11的使用 自动初始化机制 串口 LCD LVGL 连接阿里云和服务器 设备驱动 IO设备模…

多线程--简单模拟实现线程池并使用--Java

一、序言 阅读这篇博客之前建议先读多线程--线程池概念以及使用--Java-CSDN博客&#xff0c;里面有对线程池的详细介绍&#xff0c;这边就不过多赘述。 二、模拟实现固定线程数目的线程池 通过对线程池的理解&#xff0c;我们了解到线程池将我们需要执行的任务Runnable放在阻…

bert-base-chinese模型使用教程

向量编码和向量相似度展示 import torch from transformers import BertTokenizer, BertModel import numpy as npmodel_name "C:/Users/Administrator.DESKTOP-TPJL4TC/.cache/modelscope/hub/tiansz/bert-base-chinese"sentences [春眠不觉晓, 大梦谁先觉, 浓睡…

mutable用法

mutable 关键字用于允许类的某个成员变量在 const 成员函数中被修改。通常&#xff0c;const 成员函数不能改变对象的任何成员变量&#xff0c;但将成员变量声明为 mutable 可以例外 class Hero { public:Hero():m_Hp(0), m_getHpCounter(0){}int getHp() const {m_getHpCounte…

map和set和pair

目录 一.序列式容器和关联式容器 一.set set类的介绍&#xff1a; Construct &#xff1a;set的初始化 insert&#xff1a;插入 ​编辑find&#xff1a;查找 erase&#xff1a;删除 set查找范围的函数&#xff1a;​编辑 二.map 2.1map介绍 2.2pair类型介绍 在map的i…

BEV数据集标注成本高?BEVPose:减少对标注数据依赖!

引言 本文提出了一个名为BEVPose的框架&#xff0c;通过利用自监督和传感器位姿信息&#xff0c;实现相机和激光雷达数据的多模态BEV表示对齐&#xff0c;显著减少了对标注数据的依赖。BEVPose在BEV地图分割任务中表现出色&#xff0c;能够超越全监督的方法&#xff0c;同时提升…

AI - 使用LangChain构建简单LLM应用程序

AI - 使用LangChain构建简单LLM应用程序 什么是LLM LLM&#xff08;Large Language Model&#xff0c;大型语言模型&#xff09;是一种由大量文本数据训练而成的深度学习模型&#xff0c;能够理解和生成自然语言。例如&#xff0c;GPT-3就是一种流行的LLM&#xff0c;可以用于…

linux shell脚本学习(1):shell脚本基本概念与操作

1.什么是shell脚本 linux系统中&#xff0c;shell脚本或称之为bash shell程序&#xff0c;通常是由vim编辑&#xff0c;由linux命令、bash shell指令、逻辑控制语句、注释信息组成的可执行文件 *linux中常以.sh后缀作为shell脚本的后缀。linux系统中文件乃至脚本的后缀并没有…

Linux云计算 |【第五阶段】CLOUD-DAY6

主要内容&#xff1a; 了解Kubernetes的架构、搭建Kubernetes集群 一、Kubernetes 概述 Kubernetes 这个名字来自希腊语&#xff0c;意思是“舵手”或“领航员”&#xff1b;K8S 是 Kubernetes 的缩写&#xff0c;其中“8”代表字母“ubernete”中的8个字母。Kubernetes 是由…

无人机之中继通信技术篇

一、定义与原理 无人机中继通信技术是指通过无人机搭载中继设备&#xff0c;将信号从一个地点传输到另一个地点&#xff0c;从而延长通信距离并保持较好的通信质量。其原理类似于传统的中继通信&#xff0c;即在两个终端站之间设置若干中继站&#xff0c;中继站将前站送来的信号…