CF711C三维DP
题目大意:公园里有$n$棵树,每棵树有颜色$a_i$,也可能没涂颜色,现在有$m$种颜料,可以给没颜色的树涂颜色,花费以矩阵的形式给出:$a[i][j]$表示第$i$棵树涂颜色$j$的花费。连续相同的一段颜色贡献为$1$,求所有树贡献恰好为$k$的最小花费。
卡了半天的简单DP题。数据范围$100$,$O(n^4)$可写。设$dp[i][j][k]$为前$i$颗树,第$i$颗为$j$颜色,贡献为$k$的最小花费。
AC代码:
1 | int n, m, k, ans = INF; |