当前位置:网站首页>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
边栏推荐
猜你喜欢
随机推荐
list与string转换
IDEA文件UTF-8格式控制台输出中文乱码
MUV LUV EXTRA 2019CCPC Qinhuangdao Station J Question KMP
2017 G icpc shenyang Infinite Fraction Path BFS + pruning
postgresql Window Functions
Win10桌面图标排列混乱
jmeter并发数量以及压力机的一些限制
基于布朗运动的文本生成方法-LANGUAGE MODELING VIA STOCHASTIC PROCESSES
链表专项练习(四)
Four departments including the Ministry of Industry and Information Technology promote green smart home products to the countryside
74HC595芯片引脚说明
(五)、马尔科夫预测模型
C语言:调整奇数偶数顺序
排序第二节——选择排序(选择排序+堆排序)(两个视频讲解)
Change Jupyter Notebook default open directory
RK3568商显版开源鸿蒙板卡产品解决方案
failed (13: Permission denied) while connecting to upstream
洛谷P1110 报表统计 multiset stl好题
半导体新能源智能装备整机软件系统方案设计
找不到和chrome浏览器版本不同的chromedriver的解决方法