当前位置:网站首页>2019 Nanchang Internet Competition Question C, Hello 2019
2019 Nanchang Internet Competition Question C, Hello 2019
2022-08-09 07:40:00 【swust_fang】
The meaning of the question: Find the minimum number of deletions that includes 9012, but does not include 8012
Solution idea: first invert the string, and maintain the matrix for the line segment tree according to the problem solving idea
We represent each interval of the line segment tree as a matrix, and the matrix mat[5][5] maintains the situation of the 2019 sequence~
First clarify the meaning of the matrix mat: we need to form a sequence of length 4
mat[0][1] represents the minimum cost required for "2"
mat[0][2] represents the minimum cost of "20"
mat[0][3] represents the minimum cost required by "201"
mat[0][4] means "2019" and there is no minimum cost required for "2018"
Encounter a '2', then we use this '2', mat[0][1]=0, if not mat[0][1]=1
When a '0' is encountered, then we use this '0', mat[1][2]=0, if not mat[1][1]=1
Encounter a '1', then we use this '1', mat[2][3]=0, if not mat[2][2]=1
Encounter a '9', then we use this '9', mat[3][4]=0, if not mat[3][3]=1
In 2019, we can choose to transfer or not transfer our numbers, but in the case of 8, whether it is 3 or 4, it will cost 1 to delete him~
Encounter an '8', then we don't need this '8', mat[3][3]=1, mat[4][4]=1
From the case of i->j, it is obvious that the optimal can be found by shifting i->k,k->j
dp transfer equation: ans.mat[i][j]=min(ans.mat[i][j],a.mat[i][k]+b.mat[k][j]);
If you want to merge, you can directly use the line segment tree interval to merge.
This question is really difficult. After the game, I found that more than 200 teams beat the tourist~(wu
//#pragma comment (linker, "/STACK:102400000,102400000")#include#include#include#include#include#include#include#include#include#include#include
边栏推荐
猜你喜欢
C语言:打印菱形
postgresql窗口功能
错误:为 repo ‘oracle_linux_repo‘ 下载元数据失败 : Cannot download repomd.xml: Cannot download repodata/repomd.
CoCube传感器MPU6050笔记
C language: reverse character order
低成本、大容量、高交互…Polkadot 引领 GameFi 实现新突破
SA-Siam:用于实时目标跟踪的双重连体网络A Twofold Siamese Network for Real-Time Object Tracking
c语言位段
SSM整合开发案例
定时任务组件Quartz
随机推荐
P1505 [国家集训队]旅游 树链剖分
oracle存储过程问题解答
排序第四节——归并排序(附有自己的视频讲解)
4.MySQL更新和删除数据
pip安装更换镜像
【Shell】查找进程的pid并根据pid获取该进程所占用的端口号以及该进程在系统中所下达的指令名称
SAP ALV data export many of the bugs
Win10桌面图标排列混乱
View log common commands
【机器学习】降维代码练习
(四)BP神经网络预测(上)
重要消息丨.NET Core 3.1 将于今年12月13日结束支持
pytorch指定GPU
Pytorch 训练技巧
MVN 中配置flyway mysq
Important news丨.NET Core 3.1 will end support on December 13 this year
常用测试用例设计方法之正交实验法详解
设备指纹详解之识别垃圾账号
Difference Constraint - Graph Theory
Lottie系列三 :原理分析