Cities

Bob lives in a chaotic country with $n$ cities in a row, numbered from $1$ to $n$ . These cities are owned by different lords, and the $i$ -th cities currently belongs to the $a_i$ -th lord. To simply problems, we assume there are $n$ lords in the country, and they are also numbered from $1$ to $n$ . Some lords may take control of multiple cities, while some new-born lords have not got any cities yet.

Obviously, the greedy lords are not satisfied with the number of territories they have, so the country is constantly at war. Bob wants to change that, by making all the cities belong to the same lord!

Bob can perform some magical operations to support his grand plan. With the help of each magic, Bob can do the following:

Choose some cities with consecutive indices such that they belong to the same lord, and assign them to any other lord.

As magics are really tiring, Bob wants to know the minimum number of such operations he needs to use to make all the cities belong to one lord.

The following picture shows an example where $n=6$ . Different shapes are used to represent cities belonging to different lords. As shown in the picture, the minimum number of magic operations used is 2.

The first line contains a single integer $t\ (1\le t\le 160)$ --- the number of test cases.

The first line of each test case contains an integers $n\ (1\le n\le 5000)$ --- the number of cities in the country.

The second line of each test case contains n integers $a_i$ $(1\le a_i\le n)$ --- the i-th city was originally owned by the $a_i$ -th lord. It is guaranteed that $\textbf{currently no Lord will have more than 15 cities, which means no one $a_i$ will appear more than 15 times in this line.}$

It is guaranteed that the sum of n over all test cases doesn't exceed 6000.

#include<cstdio> #include<algorithm> #define rep(i,l,r) for (int i=(l); i<=(r); i++) using namespace std; const int M=5010; int n,T,a[M],dp[M][M],las[M],b[M]; int main(){ for (scanf("%d",&T); T--; ){ scanf("%d",&n); rep(i,1,n) b[i]=0; rep(i,1,n) scanf("%d",&a[i]),las[i]=b[a[i]],b[a[i]]=i; rep(i,2,n) rep(l,1,n-i+1){ int r=l+i-1,k=las[r]; dp[l][r]=1e9; while (k>=l) dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]),k=las[k]; dp[l][r]=min(dp[l][r],dp[l][r-1]+1); dp[l][r]=min(dp[l][r],dp[l+1][r]+1); } printf("%d\n",dp[1][n]); } return 0; }

详情