[SW Expert Academy] 1264. イメージ類似度

問題を読む
スキャン画像にr,g,b,kの4列を返すスキャナがある場合、2つの画像のスキャンコード列を比較して類似度を調べる.
最大の共通部分コード列を求めればいいです.
入力
テストケース数t
ワード数n(n<=500)
コード列x(n文字)
コード列y(n文字)
問題を解く
dpで解きますが、dpの概念はまだ明確ではないので、ちょっと難しいです.
しかしコードは短い.
dpテーブルの作成
n*nの表では、同じ文字が表示された場合は対角線左上+1、文字が異なる場合は左上の数字より大きい数字を書きます.
対角線左上:n-1の順序で最も一致する部分が最も多い部分の文字列の個数まで、同じ文字が現れて、ここで1をプラスするのは最大値です

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		if (copy[i-1] == origin[j-1]) {
			memo[i][j] = memo[i - 1][j - 1] + 1;
		}
		else {
			if (memo[i - 1][j] > memo[i][j - 1]) memo[i][j] = memo[i - 1][j];
			else memo[i][j] = memo[i][j - 1];
		}
	}
}

小数点をロックfixedは小数点を固定するコードであり、precision(2)は何個を固定するかを指定するコードである.下図のように小数点以下2桁まで出力できます.

cout << fixed;
cout.precision(2);

完全なコード

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int memo[501][501];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		double ans, crtic;
		int n;
		ans = 1;
		string origin, copy;
		cin >> n;
		cin >> origin;
		cin >> copy;
		memset(memo, 0, sizeof(memo));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (copy[i-1] == origin[j-1]) {
					memo[i][j] = memo[i - 1][j - 1] + 1;
				}
				else {
					if (memo[i - 1][j] > memo[i][j - 1]) memo[i][j] = memo[i - 1][j];
					else memo[i][j] = memo[i][j - 1];
				}
			}
		}
		ans = (double)memo[n][n]/(double)n*100.0;
		cout << fixed;
		cout.precision(2);
		cout << "#" << t << " " << ans<<'\n';
	}
}