第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明） Cities (区间DP)
Cities (区间DP)题目链接大致题意:一个长度为 n 的数组，一次操作可以选择一段连续值相同的区间，使其变成其他值，问最少需要多少次操作，才能使得数组的值全相等数组中每个数最多出现15次解题思路:首先将数组去重,使得相邻元素不同,定义last[i]表示为上一次a[i]出现的位置(这是关键,因为我们要尽量减少操作次数,所以我们尽可能选择左右端点相同的进行操作)有f[l+1][r]+1和f[l][r-1]+1两种转移,我们定左端点,从右往左进行dp,即f[l][r] = f[l][r - 1
