[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology