Codeforces #743 Div1 : C. Paint

こっちは何とか解けた。
https://codeforces.com/contest/1572/problem/C

問題

1*Nの形状に並んだマス目があり、それぞれのマスの初期状態の色が与えられる。
ただし、１つの色が使われたマスは20個以下である。

以下の手順を繰り返し、全マス同色にしたい。
最小で何回手順を行う必要があるか。

• 色を1つ選ぶ。
• マスを１つ選び、そのマスと同色のマスでつながる一連のマスを、選んだ色で上書きする。

解法

f(L,R) := マス目の区間[L,R)をR-1番のマス目と同じ色でそろえるまでの最小手順回数
とする。f(0,R)が解となる。

f(L,R)は以下の最小値となる。

• f(L,R-1)+1
• A[M-1]=A[R-1]の時、f(L,M)+f(M,R)

同じ色の登場頻度をFとすると、Mは高々F通り考えればよく、全体でO(N^2*F)程度の計算量で済む。

int T,N;
int A[3030];
int dp[3030][3030];
vector<int> pre[3030];
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) pre[i].clear();
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			if(i&&A[i]==A[i-1]) {
				i--;
				N--;
			}
		}
		for(int R=1;R<=N;R++) {
			for(int L=0;L<R-1;L++) dp[L][R]=dp[L][R-1]+1;
			dp[R-1][R]=0;
			FORR(p,pre[A[R-1]]) {
				for(int L=0;L<p;L++) {
					dp[L][R]=min(dp[L][R],dp[L][p]+dp[p][R-1]+1);
				}
			}
			/*
			cout<<R<<" ";
			for(int L=0;L<R;L++) cout<<L<<":"<<dp[L][R]<<" ";
			cout<<endl;
			*/
			pre[A[R-1]].push_back(R);
		}
		cout<<dp[0][N]<<endl;
		
	}
}

まとめ

1750ptだけどなんとか解けて良かった。