本题解同步更新于我的博客欢迎围观★,°:.☆( ̄▽ ̄)/$:.°★

抽象题意

题目有点长,我们需要抽象出一个模型:

一个长度为nn的序列aia_i,从a1a_1开始向后跳,每次可以从aia_i跳到下一位ai+1a_{i+1},或者跳到与aia_i相同数字的任何一位。求跳到最后一位ana_n所需的最小次数。

思路

为了方便我们记每一位的数字称为该位的颜色

从抽象出的模型可以看出,每一位所需的次数,即为跳到前一位所需次数与跳到同颜色所需最小次数之间的最小值,再加一

那我们用一个数组tim[i]tim[i]记录每一位所需最小次数,以及每种颜色所需次数最小的位置col[i]col[i](不直接记次数是因为第一次扫到这个颜色的时候,不知道这个跳到这里所需的次数为多少)

但是我们从前往后扫的话,实际上跳到同颜色所需次数最小的一位有可能在这一位的后面,我们怎么办呢,可以一直扫,直到每一位都确定下来,没有再更改为止

代码

#include<bits/stdc++.h>
#define MAXn 1000001
#define MAXk 110
#define inf 200000000
using namespace std;

int n;
int a[MAXn];
int tim[MAXn];//每位所需次数
int col[MAXk];//走到颜色i次数最小的位置 

inline int minn(int x, int y)//手写min函数,更快 
{
	if(x < y)
		return x;
	else return y;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		tim[i] = inf;
	}
	
	tim[1] = 0;
	col[a[1]] = 1;
	bool if_do = 1;
	while(if_do)//一直去刷新看什么时候没有更改 
	{
		if_do = 0;
		for(int i = 2; i <= n; i++)//第一位肯定是确定的,从第二位开始 
		{
			int tmp = tim[i];//先存下这个数,等会看看有没有被更改 
			if(col[ a[i] ])//如果这个颜色走过
				tim[i] = tim[ col[ a[i] ] ] + 1;//先假设,这一位的最小次数,是由同颜色次数最小的一个位置跳过来的
			else col[ a[i] ] = i;//第一次出现,那他应该是当前该颜色所需次数最小的 一位
			tim[i] = minn( tim[i - 1] + 1, tim[i] );//看看从上一位走来是不是更快 
			if(tim[i] < tim[ col[ a[i] ] ]) //如果这一位所需的次数,比这一位颜色所需的最小,更新
				col[ a[i] ] = i; 
			if(tmp != tim[i]) 
				if_do = 1;//更新了继续做 
		}
	}
	printf("%d", tim[n]);
	
	return 0; 
}