A45691. 神奇的数列一个正整数数列， 可以将它切割成若干个数据段， 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于， 每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 7 7 6 9 4” 中切除数据段“7 7 ” 后， 余下的元素会构成数列“2 8 9 6 9 4”请问若要将该数列切割成若干个数据段， 则至少会切出来几个数据段？样例： 按下列顺序切割数列…
填空题
较难
知识点
题目描述
神奇的数列
一个正整数数列， 可以将它切割成若干个数据段， 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于， 每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 7 7 6 9 4” 中切除数据段“7 7 ” 后， 余下的元素会构成数列“2 8 9 6 9 4”请问若要将该数列切割成若干个数据段， 则至少会切出来几个数据段？
样例： 按下列顺序切割数列“2 8 9 7 7 6 9 4” ， 只要切割成 6 段
切割出“7 7” ， 余下 “2 8 9 6 9 4”
切割出 “6” ， 余下 “2 8 9 9 4”
切割出 “9 9” ， 余下 “2 8 4”
切割出 “2” ， 余下 “8 4”
切割出 “8” ， 余下 “4”
时间限制： 1000
内存限制： 65536
输入
第一行是一个整数， 示共有多少组测试数据。 每组测试数据的输入包括两行： 第一行是整数 N, N<=200,表示数列的长度， 第二行是 N 个正整数。
输出
每个测试案例的输出占一行， 是一个整数。 格式是： Case n: x n 是测试数据组编号， x 是答案
样例输入
2
8
2 8 9 7 7 6 9 4
16
2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
样例输出
Case 1: 6
Case 2: 11
参考答案
#include <iostream>
#include <cstring>
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("\n");//cout << endl;
}*/
printf("Case %d: %d\n", T0-T, score[0][N-1]);
//cout << "Case " << T0-T << ": " <<score[0][N-1] << endl;
}
return 0;
}
上一题
下一题