简答题 偏难
#7307

神奇的数列 一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素…

神奇的数列

一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后, 余下的元素会构成数列“2 8 9 6 94”

请问若要将该数列切割成若干个数据段, 则至少会切出来几个数据段?

样例: 按下列顺序切割数列“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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int score[202][202]; int N; int num[202]; int main() {   int T;   // cin &gt;&gt; T;   // freopen("C:\\Users\\csctest\\Desktop\\slin.txt", "r", stdin);   // freopen("C:\\Users\\csctest\\Desktop\\sloutx.txt", "w", stdout);   scanf("%d", &amp;T);   int T0 = T;   while (T--) {     /*for (int i = 0; i &lt; N; ++i) {             for (int j = 0; j &lt; N; ++j) {                     score[i][j] = 256;             }     }*/     memset(score, 1, sizeof(score));     memset(num, 0, sizeof(num));     int N;     scanf("%d", &amp;N); // cin &gt;&gt; N;     for (int i = 0; i &lt; N; ++i) {       scanf("%d", &amp;num[i]); // cin &gt;&gt; num[i];       score[i][i] = 1;     }     for (int i = 0; i &lt; N; ++i) {       for (int j = 0; j &lt; i; ++j) {         score[i][j] = 0;       }     }     for (int i = 0; i &lt; 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 &gt;= 0; --i) {       for (int j = i + 1; j &lt; N; ++j) {         for (int k = i; k &lt; 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 &lt; N; ++i) {             for (int j = 0; j &lt; N; ++j) {                     if (score[i][j] &lt; 10000 ) printf("%d ", score[i][j]);//cout     &lt;&lt; score[i][j] &lt;&lt; " "; else printf("%d ", -1); //cout &lt;&lt; -1 &lt;&lt; " ";             }             printf("\n");//cout &lt;&lt; endl;     }*/     printf("Case %d: %d\n", T0 - T, score[0][N - 1]);     // cout &lt;&lt; "Case " &lt;&lt; T0-T &lt;&lt; ": " &lt;&lt;score[0][N-1] &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。