摘要
Title: 3996. 涂色
Tag: 区间dp
Memory Limit: 64 MB
Time Limit: 1000 ms

3996. 涂色

题意

首开始的时候从连通块中，选择一个作为起点，此后做的扩展操作，都是从这个连通块往边上扩展(就是改起点连通块的颜色)。
思路

更清晰的情况：
- 最终扩展到i
- 最终扩展到j
- 最终i,j被同时扩展到
最终的dp递推式
$f[i][j] = \begin{cases} & \text{f[i][j] = min(f[i+1][j], f[i][j-1])+1} \\ c[i]== c[ j]&\text{f[i][j] = min(f[i][j],f[i+1][j-1]+ 1)} \end{cases}$

代码

'''
Author: NEFU AB-IN
Date: 2023-03-24 17:07:53
FilePath: \Acwing\3996\3996.py
LastEditTime: 2023-03-24 19:48:13
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(5e3 + 10)
INF = int(2e9)

n = int(input())
c1 = list(read())
c = [0]
dp = [[0] * N for _ in range(N)]

for i in range(n):
    if i == 0 or c1[i] != c1[i - 1]:
        c.append(c1[i])

n = len(c) - 1
for len in range(2, n + 1):
    l, r = 1, len
    while r <= n:
        dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + 1
        if c[l] == c[r]:
            dp[l][r] = min(dp[l][r], dp[l + 1][r - 1] + 1)
        l += 1
        r += 1

print(dp[1][n])

3996. 涂色

题意

思路

代码