傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個(gè)有$n$個(gè)像素的圖像，每個(gè)像素都有一個(gè)顏色$a_i$，保證每種顏色的圖像不會(huì)超過$20$個(gè)。你現(xiàn)在每次可以選擇一個(gè)顏色，并選擇一段連續(xù)的像素，要求連續(xù)的像素的顏色必須相同，讓后將這段像素變成選擇的顏色，問最少需要進(jìn)行多少次操作，才能使得所有像素的顏色相同。

$1\le n\le 3e3,1\le a_i\le n$

思路：

考慮$[a,b,a]$這種形式的，肯定是將$b$變成$a$是最優(yōu)的，而不是將$a$變成$b$，再看一下數(shù)據(jù)范圍，就能確定是一個(gè)$20?n^2$的區(qū)間$dp$了。

設(shè)$dp[i][j]$代表將$[i,j]$變成一種顏色的最少操作次數(shù)，根據(jù)上面的分析，我們將所有顏色變成兩頭的顏色答案一定不劣，所以先不管端點(diǎn)什么顏色，容易寫出來其中的一個(gè)轉(zhuǎn)移方程$f[i][j]=min(f[i][j?1]+1,f[i+1][j]+1)$，因?yàn)榭梢詫⑵溆鄥^(qū)間的所有顏色都變成端點(diǎn)顏色，為了方便我們假設(shè)將其都變成左端點(diǎn)的顏色。

考慮每種顏色都不會(huì)超過$20$個(gè)，由于將其變成左端點(diǎn)的顏色，所以暴力枚舉與左端點(diǎn)顏色相同的點(diǎn)，然后將其分成兩個(gè)區(qū)間進(jìn)行轉(zhuǎn)移即可。

復(fù)雜度$O(20n^2)$

// Problem: E. Paint // Contest: Codeforces - Codeforces Round #743 (Div. 2) // URL: https://codeforces.com/contest/1573/problem/E // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=3010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int f[N][N]; int a[N],ne[N]; int pos[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);while(_--) {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=0;for(int i=n;i>=1;i--) {if(!pos[a[i]]) ne[i]=n+1;else ne[i]=pos[a[i]];pos[a[i]]=i; }for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) f[i][j]=INF; else f[i][j]=0;for(int len=2;len<=n;len++) {for(int l=1;l+len-1<=n;l++) {int r=l+len-1;f[l][r]=min(f[l+1][r]+1,f[l][r-1]+1);for(int k=ne[l];k<=r;k=ne[k]) {f[l][r]=min(f[l][r],f[l][k-1]+f[k][r]);}}}printf("%d\n",f[1][n]);}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #743 (Div. 2) E. Paint 区间dp + 暴力的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。