[TIOJ] 1914. 彩色紙條

題目連結:https://tioj.infor.org/problems/1914

---

搞了好久，才發現我一開始的DP式是錯的QQ
這題難點應該就是DP式吧，不過我也不知道我怎麼想到的，所以這邊就給式子就好：$dp[i][j] = \min_{i \leq k < j }(dp[i][k]+dp[k+1][j])-[a_i==a_j]$(其中[]是艾佛森括號)，然後$dp[i][j]$的意思是把$[i, j]$填滿的最小步數，然後轉移方法就是枚舉中點，代表先把$[i, k]$填好再填$[k+1, j]$，而減一的部份則是因為明顯若首尾相同，那我們在填左邊的時候就可以順便拉一條過去到右邊，就不需要右邊又在畫一遍了。

#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5;

int arr[N], dp[N][N];

int main(){
	int t; scanf("%d", &t);
	while(t--){
		int n, m; scanf("%d%d", &n, &m);
		for(int i=1;i<=n;i++)
			scanf("%d", arr+i);
		for(int i=1;i<=n;i++) dp[i][i]=1;
		for(int i=n;i>=1;i--){
			for(int j=i+1;j<=n;j++){
				dp[i][j]=1<<25;
				for(int k=i;k+1<=j;k++)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
				if(arr[i]==arr[j]) dp[i][j]--;
			}
		}
		printf("%d\n", dp[1][n]);
	}
	return 0;
}

C++