目錄

原題：

時間：1s? ?空間：256M

題目描述

輸入格式

輸出格式

樣例輸入

樣例輸出

題目大意：

主要思路：

dp轉移：

dp初始化：

代碼：

---

原題：

時間：1s? ?空間：256M

題目描述

大哈是個游戲王，盡管他的水平一言難盡，但他卻總是這樣自我稱呼。小羽說如果你能把這個游戲通關了，你才算是個真的游戲王。這個游戲一開始你有n個連在一起的顏色塊，第i個顏色塊的顏色為。如果從i到j的顏色都一樣，就說明i到j屬于同一個連通塊。比如[5,5,5]屬于同一個連通塊，[4,3,9,9]有3個連通塊。游戲開始前大哈可以選擇任意一個位置作為起始點，然后開始游戲。游戲的每一輪大哈可以將包含起始點的連通塊的顏色變成任意一種其他的顏色。問大哈能將整個數組變成從1到n的連通塊所需要的最少回合數。

大哈是個游戲王，盡管他的水平一言難盡，但他卻總是這樣自我稱呼。小羽說如果你能把這個游戲通關了，你才算是個真的游戲王。這個游戲一開始你有n個連在一起的顏色塊，第i個顏色塊的顏色為。如果從i到j的顏色都一樣，就說明i到j屬于同一個連通塊。比如[5,5,5]屬于同一個連通塊，[4,3,9,9]有3個連通塊。游戲開始前大哈可以選擇任意一個位置作為起始點，然后開始游戲。游戲的每一輪大哈可以將包含起始點的連通塊的顏色變成任意一種其他的顏色。問大哈能將整個數組變成從1到n的連通塊所需要的最少回合數。

輸入格式

第一行一個整數n（）

第二行n個整數（）

輸出格式

一個整數代表最少回合數

樣例輸入

4

5 2 2 1

樣例輸出

2

題目大意：

給你n個數，要你求把所有數變成相同一個數所需的最小操作數（每次操作可以將包含起點的連通塊變為同一個數）

主要思路：

這題很難想到區間dp，我們用dp[l][r] 表示把l~r里的數變為同一個數的最小操作數，首先把每個連通塊去重（就像把【2，2，3，3，2，2，4，4，4，4】變成【2，3，2，4】。

dp轉移：

1. v[l] == v[r] 那么就要dp[l][r] = dp[l+1][r-1]+1;注意：a[l+1]!=a[l],a[r-1]!=a[r]圖：（畫的有點草，謝謝諒解）

   

2. 否則dp[l][r] = min(dp[l+1][r],dp[l][r-1])+1;圖：（畫的有點草，謝謝諒解）

   

剩下就沒有什么好說的了

dp初始化：

dp[i][i] = 0把自己變成同一個數需要0步（i<=n)

代碼：

#include<bits/stdc++.h>
using namespace std;
vector<int> v; 
int dp[5010][5010];
int main()
{int n;cin>>n;v.push_back(0);int num=-1;for(int i=1;i<=n;i++){int x;cin>>x;if(i == 1){num=x;}else{if(x == num){}else{v.push_back(x);num = x;}}}memset(dp,0x3f,sizeof(dp));for(int i=1;i<=v.size();i++){dp[i][i] = 0;}for(int len=2;len<=v.size();len++){for(int l=1;l+len-1<=v.size();l++){int r=l+len-1;if(v[l] == v[r]&&dp[l-1][r-1]!=v[l]&&dp[l-1][r-1]!=v[r]){dp[l][r] = dp[l+1][r-1]+1;}else{dp[l][r] = min(dp[l+1][r],dp[l][r-1])+1;}}}cout<<dp[1][v.size()];return 0;
}