Codeforces ECR #161 : F. Replace on Segment

ちょっとややこしい。
https://codeforces.com/contest/1922/problem/F

問題

N要素の整数列Aと、整数Kが与えられる。
Aの各要素は1～Kのいずれかである。
ここで、Aの部分列A[L,R]を選択し、それらのいずれでもない1～Kのいずれかの整数値に置き換える、という処理を任意回数おこなえる。

Aの全要素をそろえるのに必要な最小処理数を求めよ。

解法

f(L,R,v) := A[L...R]をvにそろえるのに必要な最小処理数
g(L,R,v) := A[L...R]をいずれもv以外するのに必要な最小処理数

として、DPでこれらを埋めて行くことを考える。

• f(L,R,v) ≦ f(L,M,v)+f(M,R,v)
• g(L,R,v) ≦ g(L,M,v)+g(M,R,v)

なのは明らかなので、区間の短い順にこの値を求めて行けばよいのは明らか。
あとはv!=wに対し、以下の関係がある。

• f(L,R,v) ≦f(L,R,w)+1
• f(L,R,v) ≦g(L,R,v)+1
• g(L,R,v) ≦ f(L,R,v)+1
• g(L,R,v) ≦ f(L,R,w)

これらの関係は循環しているので、ダイクストラ法の要領で値の小さい順に確定させていけばよい。

int T,N,X,A[101];
int dp[102][102][102];
int dp2[102][102][102];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
		}
		FOR(x,N+1) FOR(y,N+1) FOR(k,X) dp[x][y][k]=dp2[x][y][k]=101010;
		FOR(i,N) {
			FOR(j,X) {
				if(A[i]==j) {
					dp[i][i+1][j]=0;
					dp2[i][i+1][j]=1;
				}
				else {
					dp[i][i+1][j]=1;
					dp2[i][i+1][j]=0;
				}
			}
		}
		for(int len=2;len<=N;len++) {
			for(x=0;x+len<=N;x++) FOR(y,X) {
				for(k=x+1;k<x+len;k++) {
					chmin(dp[x][x+len][y],dp[x][k][y]+dp[k][x+len][y]);
					chmin(dp2[x][x+len][y],dp2[x][k][y]+dp2[k][x+len][y]);
				}
			}
			for(x=0;x+len<=N;x++) {
				priority_queue<pair<int,int>> Q;
				FOR(y,X) {
					Q.push({-dp[x][x+len][y],y*2});
					Q.push({-dp2[x][x+len][y],y*2+1});
				}
				while(Q.size()) {
					int co=-Q.top().first;
					int id=Q.top().second%2;
					y=Q.top().second/2;
					Q.pop();
					if(id==0) {
						FOR(k,X) if(k!=y&&chmin(dp2[x][x+len][k],co)) Q.push({-dp2[x][x+len][k],2*k+1});
					}
					else {
						if(chmin(dp[x][x+len][y],co+1)) Q.push({-dp[x][x+len][y],2*y});
					}
				}
			}
		}
		int mi=1<<20;
		FOR(x,X) mi=min(mi,dp[0][N][x]);
		cout<<mi<<endl;
	}
}

まとめ

g(L,R,v)を思いつけるかがポイントだな…。