第7回ブルーブリッジカップ省試合C++A組パスワード脱落

1822 ワード

ブルーブリッジカップ文字列 LCS ダイナミック？プログラム

暗号が脱落したX星の考古学者は古代に残された暗号を発見した.これらの暗号はA,B,C,Dの4種類の植物の種子からなる配列である.よく分析すると、これらの暗号列は当初前後対称であるべきである(すなわち、私たちが言ったミラー列である).年代が古いため、多くの種が脱落し、ミラーの特徴を失う可能性があります.あなたの任務は:今見ている暗号列を与えて、当初の状態から、少なくとも何個の種が抜けてこそ、今の姿になる可能性があるかを計算することです.
現在表示されている暗号列(長さ1000以下)に正の整数を出力する必要があることを示す行を入力し、少なくともどれだけのシードが脱落したかを示します.
例えば、入力:ABCBAはプログラム出力:0
例えば、入力:ABDCBABC則プログラム出力:3
リソース約定:ピークメモリ消費<256 M CPU消費<1000 ms
要求通りに出力してください.ヘビを描いて印刷しないでください.「入力してください.」と入力します.すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.注意:main関数は0を返す必要があります注意:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特殊な関数を呼び出さないでください.注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.

考え方:前の考え方にバグがあったので、ここを大修理します.暗号列は最初は対称であり、次に最低脱落シード数が要求されるため、入力された文字列s 1を逆順序にして文字列s 2を得ることができ、2つの文字列を最長共通サブシーケンス、すなわち、順序的に何ビット同じ(不連続)かを見て、最終的な答えは文字列の長さから最長共通サブシーケンスの長さを減算することである.参考になるのは、https://blog.csdn.net/Void_worker/article/details/79734536
コード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include  
#include
using namespace std;

int dp[1000][1000];

int LCS(string x, string y)
{
	for (int i = 1; i <= x.size(); i++)
	{
		for (int j = 1; j <= y.size(); j++)
		{
			if (x[i] == y[j])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
		}
	}
	return dp[x.size()][y.size()];
}

int main()
{
	string s1, s2;
	cin >> s1;
	s2 = s1;
	reverse(s2.begin(), s2.end());
	int ans = s1.size() - LCS(s1, s2);
	cout << ans << endl;
	return 0;
}

JSOnObjectとJSOnArrayのkey値を大文字または小文字に変換する一般的な方法

ネットワーク転送中にスペース、プラス記号が生成されます