問題解決報告......?不思議な数列

最近、いくつかのことが起こったことに加えて、他の科の期末試験を準備したことで、2週間もプログラミングがほとんどなく、アルゴリズム能力が直線的に低下していることがわかりました.あさっての試験を心配し始めました.たぶん涼しいです.はい、本文です.正の整数数列を記述し、値が同じ隣接要素からなる複数のデータセグメントに切断できます.この数列の不思議な点は、1つのデータセグメントを切除するたびに、データセグメントの前後の要素が自動的に接続されて隣人になることである.例えば、数列「2 8 9 7 7 6 9 4」からデータ段「7 7」を切除すると、残りの要素が数列「2 8 9 6 9 4」を構成します.この数列をいくつかのデータ段に切断するには、少なくともいくつかのデータ段が切り出されますか?サンプル:以下の順序で「2 8 9 7 7 6 4」列をカットし、6段にカットして「7 7 7」、残りの「2 8 9 6 9 4」は「6」、残りの「2 8 8 9 4」は「9 9」、残りの「2 8 4」は「2」、残りの「8 4」は「8」、残りの「4」をカットします.
最初の行を入力すると、テストデータのセット数を示す整数になります.各試験データのセットの入力は、2行を含む.第1行は整数N、N<=200であり、数列の長さを表し、第2行はN個の正の整数である.出力各テストケースの出力は1行を占め、整数です.形式は:Case n:xnはテストデータ群番号、xは解答サンプル入力2 8 8 8 9 7 6 9 4 16 2 8 9 7 7 6 9 4 4 4 8 4 4 2 7 9サンプル出力Case 1:6 Case 2:11
自分のゲージが本当に弱いことに気づいた.この問題をするとき、最初は講義の中のボックスゲームのやり方をしようとしたが、その問題がどうしたのかすっかり忘れてしまったことに気づいた.実は郭神の標答にはパラメータが1つ足りないので、考えやすいです.そして私が書いたのはプッシュ式です.状態遷移方程式はif num[k]==num[j]score[i][j]=min{score[i][k]+score[k+1][j-1]}else score[i][j]=min{score[i][j],score[i][k]+score[k+1][j]}が最初は間違っていた.num[k]=num[j]の場合の私の状態遷移方程式はscore[i][j]=min{score[i][k-1]+score[k+1][j-1]+1,score[i][j]}今から見れば知的障害も比類がないようだが...考えているのは真ん中のブロックと後ろのブロックが一緒に消えることだ......実は真ん中のブロックが前のブロックとつながっているのか......酔っ払っている......この問題は積み木の問題より実際には長さ変数が欠けている.長さにかかわらず、最後の結果は同じだからだ.例えばABAABの場合、いろいろな消法がありますが、二つの消法の結果は同じですが、そのボックスゲームはだめです.つまり、このテーマの目的はできるだけ数列の数字を合併させることであり、合併の結果は必ず合併しない結果より良いが、ボックスゲームは本当に必ずしもそうではない.そのため、右の大きな塊の長さを加えて、誰が合併するか、合併回数(合併の代価は異なるが、この問題は同じ)を列挙するには、emmm感覚が問題をはっきり言っていない.大まかな意味では,この問題のscore[i][j]は最適サブ構造性があり,全体的に最適であるのは局所的な最適解に違いない(後には同じ色の数字が直接前の代価が最小のその数字と統合されている).しかし、ボックスゲームはこの性質を満たしていない.消すかどうかは長さにも関係します.はい、くだらないことは言わないでください.ACコードは以下の通りです.

#include 
#include 
using namespace std;
int score[202][202];
int N;
int num[202];
int main () {
	int T;
	//cin >> T;
	//freopen("C:\\Users\\csctest\\Desktop\\slin.txt", "r", stdin);
	//freopen("C:\\Users\\csctest\\Desktop\\sloutx.txt", "w", stdout); 
	scanf("%d", &T);
	int T0 = T;
	while (T--) {
		/*for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				score[i][j] = 256;
			}
		}*/
		memset(score, 1, sizeof(score));
		memset(num, 0, sizeof(num));
		int N;
		scanf("%d", &N); //cin >> N;
		for (int i = 0; i < N; ++i) {
			scanf("%d", &num[i]); //cin >> num[i];
			score[i][i] = 1;
		}
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < i; ++j) {
				score[i][j] = 0;
			}
		}
		for (int i = 0; i < N-1; ++i) {
			if (num[i] == num[i+1]) score[i][i+1] = 1;
			else score[i][i+1] = 2;
		}
		for (int i = N - 2; i >= 0; --i) {
			for (int j = i + 1; j < N; ++j) {
				for (int k = i; k < j; ++k) {
					if (num[k] == num[j]) {
						score[i][j] = min(score[i][j], score[i][k] + score[k+1][j-1]);
					}
					score[i][j] = min(score[i][j], score[i][k] + score[k+1][j]);
				}
			}
		}
		/*
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (score[i][j] < 10000 ) printf("%d ", score[i][j]);//cout << score[i][j] << " ";
				else printf("%d ", -1); //cout << -1 << " ";
			}
			printf("
");//cout << endl;
		}*/
		printf("Case %d: %d
", T0-T, score[0][N-1]);
		//cout << "Case " << T0-T << ": " <

私が書いたコードにはもう一つ問題がありますが、撮ったときに気づいたのは...初期値の設定問題です.scoreその配列は全部大きな数を設定して、プッシュする時j