AtCoder ABC #185 : E - Sequence Matching

いつもより簡単目。
https://atcoder.jp/contests/abc185/tasks/abc185_e

問題

2つの数列A,Bがある。
両者いくつか要素を削除して間を詰めた数列A',B'を作り、両要素数が同じようにする。

その際にかかるコストを、削除した要素数と、A'[i]!=B'[i]となるiの個数の和とする。
コストの最小値を求めよ。

解法

LCSと同じ要領でDPを行う。
LCSでは文字が一致すると値が1増えるが、こちらは値が増える条件が異なる点に注意。

int N,M;
int A[1010],B[1010];

int dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	FOR(x,N+1) FOR(y,M+1) dp[x][y]=1<<30;
	dp[0][0]=0;
	FOR(x,N+1) FOR(y,M+1) {
		if(x+1<=N) dp[x+1][y]=min(dp[x+1][y],dp[x][y]+1);
		if(y+1<=M) dp[x][y+1]=min(dp[x][y+1],dp[x][y]+1);
		if(x+1<=N&&y+1<=M) dp[x+1][y+1]=min(dp[x+1][y+1],dp[x][y]+(A[x]!=B[y]));
	}
	cout<<dp[N][M]<<endl;
	
	
	
}

まとめ

変な遠回りして2WAしてしまった。