2019 Nanchang Internet Competition Question C, Hello 2019

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