F. Replace on Segment
time limit per test 3 seconds
memory limit per test 256 megabytes
input: standard input
output: standard output
You are given an array
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1?,a2?,…,an?, where each element is an integer from 1 to
x
x
x.
You can perform the following operation with it any number of times:
- choose three integers
l
,
r
l, r
l,r and
k
k
k such that
1
≤
l
≤
r
≤
n
1le lle rle n
1≤l≤r≤n，
1
≤
k
≤
x
1le kle x
1≤k≤x and each element
a
i
a_i
ai? such that
l
≤
i
≤
r
lle ile r
l≤i≤r is different from
k
k
k. Then, for each
i
∈
[
l
,
r
]
iin[l,r]
i∈[l,r], replace ai with
k
k
k.
In other words, you choose a subsegment of the array and an integer from
1
1
1 to
x
x
x which does not appear in that subsegment, and replace every element in the subsegment with that chosen integer.
Your goal is to make all elements in the array equal. What is the minimum number of operations that you have to perform?
Input
The first line contains one integer
t
(
1
≤
t
≤
100
)
t (1le tle100)
t(1≤t≤100) — the number of test cases.
Each test case consists of two lines:
- the first line contains two integers
n
n
n and
x
x
x
(
1
≤
x
≤
n
≤
100
)
(1le xle nle100)
(1≤x≤n≤100);
- the second line contains
n
n
n integers
a
1
,
a
2
,
…
,
a
n
(
1
≤
a
i
≤
x
)
a_1,a_2,…,a_n (1le a_ile x)
a1?,a2?,…,an?(1≤ai?≤x).
Additional constraint on the input: the sum of
n
n
n over all test cases does not exceed
500
500
500.
Output
For each test case, print one integer — the minimum number of operations you have to perform.
Example
input
3
3 2
1 2 1
6 3
1 2 3 1 2 3
12 3
3 1 3 1 2 1 1 2 3 1 1 3
output
1
2
2
思路：区间DP。
d
[
l
]
[
r
]
[
c
]
d[l][r][c]
d[l][r][c]表示区间
[
l
,
r
]
[l,r]
[l,r]内的数都变为
c
c
c的最小操作次数，
f
[
l
]
[
r
]
[
c
]
f[l][r][c]
f[l][r][c]表示区间
[
l
,
r
]
[l,r]
[l,r]内不包含
c
c
c的最小操作次数，则转移方程如下:
d
l
,
r
,
c
=
min
?
l
≤
k
<
r
(
d
l
,
k
,
c
+
d
k
+
1
,
r
,
c
,
f
l
,
k
,
c
+
d
k
+
1
,
r
,
c
+
1
,
d
l
,
k
,
c
+
f
k
+
1
,
r
,
c
+
1
,
f
l
,
k
,
c
+
f
k
+
1
,
r
,
c
+
1
)
f
l
,
r
,
c
=
min
?
l
≤
k
<
r
(
d
l
,
k
,
c
+
d
k
+
1
,
r
,
c
+
1
,
f
l
,
k
,
c
+
d
k
+
1
,
r
,
c
+
1
,
d
l
,
k
,
c
+
f
k
+
1
,
r
,
c
+
1
,
f
l
,
k
,
c
+
f
k
+
1
,
r
,
c
)
f
l
,
r
,
c
=
min
?
k
≠
c
d
l
,
r
,
k
egin{aligned} d_{l,r,c}=&min_{lle klt r}(d_{l,k,c}+d_{k+1,r,c} , f_{l,k,c}+d_{k+1,r,c}+1 , d_{l,k,c}+f_{k+1,r,c}+1 , f_{l,k,c}+f_{k+1,r,c}+1)\ f_{l,r,c}=&min_{lle klt r}(d_{l,k,c}+d_{k+1,r,c}+1 , f_{l,k,c}+d_{k+1,r,c}+1 , d_{l,k,c}+f_{k+1,r,c}+1 , f_{l,k,c}+f_{k+1,r,c})\ f_{l,r,c}=&min_{k
e c} d_{l,r,k} end{aligned}
dl,r,c?=fl,r,c?=fl,r,c?=?l≤k<rmin?(dl,k,c?+dk+1,r,c? , fl,k,c?+dk+1,r,c?+1 , dl,k,c?+fk+1,r,c?+1 , fl,k,c?+fk+1,r,c?+1)l≤k<rmin?(dl,k,c?+dk+1,r,c?+1 , fl,k,c?+dk+1,r,c?+1 , dl,k,c?+fk+1,r,c?+1 , fl,k,c?+fk+1,r,c?)k=cmin?dl,r,k??复杂度
O
(
x
?
n
3
)
O(x*n^3)
O(x?n3)。
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=1e5+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX/2;
const double PI=acos(-1.0);
typedef long long ll;
int d[110][110][110];
int f[110][110][110];
int solve()
{
int n,x;
cin>>n>>x;
vector<int>a(n+1);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=x;k++)d[i][j][k]=f[i][j][k]=INF;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=x;j++)d[i][i][j]=1,f[i][i][j]=0;
d[i][i][a[i]]=0;
f[i][i][a[i]]=1;
}
auto Min=[](int &x,int y){x=min(x,y);};
for(int len=2;len<=n;len++)
for(int i=1,j=len;j<=n;i++,j++)
for(int k=i;k<j;k++)
{
for(int c=1;c<=x;c++)
{
Min(d[i][j][c],d[i][k][c]+d[k+1][j][c]);
Min(d[i][j][c],f[i][k][c]+d[k+1][j][c]+1);
Min(d[i][j][c],d[i][k][c]+f[k+1][j][c]+1);
Min(d[i][j][c],f[i][k][c]+f[k+1][j][c]+1);
Min(f[i][j][c],d[i][k][c]+d[k+1][j][c]+1);
Min(f[i][j][c],f[i][k][c]+d[k+1][j][c]+1);
Min(f[i][j][c],d[i][k][c]+f[k+1][j][c]+1);
Min(f[i][j][c],f[i][k][c]+f[k+1][j][c]);
}
int p=INF,s=INF;
for(int c=1;c<=x;c++)Min(f[i][j][c],p),Min(p,d[i][j][c]);
for(int c=x;c>=1;c--)Min(f[i][j][c],s),Min(s,d[i][j][c]);
}
return printf("%d
",*min_element(d[1][n]+1,d[1][n]+x+1));
}
int main()
{
int T=1;
cin>>T;
while(T--)solve();
return 0;
}