题目描述
Blotch修建了一面墙。
墙由 N 个部分构成,从左到右依次编号 1 到 N。
由于他修建的十分匆忙,墙的各个部分高度可能并不相同。
第 i 个部分墙体的高度用 Ai 来表示。
Blotch想要通过重建部分墙面,从而对墙进行修整。
他可以将任意部分的墙面重修为任意高度。
重修完成之后,如果满足 Ai≠Ai+1 的 i (1≤i<N) 的数量不超过 k,他将会十分高兴。
在满足能够使得Blotch十分高兴的前提下,最少需要重建多少部分墙面?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组测试数据共两行,第一行包含整数 N 和 k。
第二行包含 N 个整数,其中第 i 个整数表示第 i 部分墙体的高度 Ai。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为最少需要重建的墙面数量。
数据范围
1≤T≤100,
1≤Ai≤1000,
0≤k≤N,
2≤N≤100
样例
4
8 2
300 100 300 300 200 100 800 500
5 3
100 100 100 100 3
7 3
10 20 40 10 10 30 30
10 2
30 30 60 60 90 90 60 60 30 30
Case #1: 3
Case #2: 0
Case #3: 1
Case #4: 2
算法1
(动态规划) $O(n^4)$
dp[ i ][ j ][ k ]表示前i个墙且第i个墙以高度j结尾,不同的个数为k时的最小更改高度
先将高度离散化100以内
初始化 dp[ 1 ][ height[ 1 ] ][ 0 ] = 0;
dp[ 1 ][ other ][ 0 ] = 1;
然后剩下就是类似背包的那种递推
C++ 代码
//可过kickstart大数据
#include<bits/stdc++.h>
using namespace std;
int T, N, K;
int A[ 110 ], B[ 110 ];
map< int, int > Index;
int dp[ 101 ][ 101 ][ 101 ];
int main()
{
cin >> T;
for( int i = 1; i <= T; i ++ )
{
cin >> N >> K;
int num = 0;
Index.clear();
for( int j = 1; j <= N; j ++ )
{
cin >> A[ j ];
if( Index[ A[ j ] ] ) B[ j ] = Index[ A[ j ] ];
else
{
Index[ A[ j ] ] = ++ num;
B[ j ] = Index[ A[ j ] ];
}
}
dp[ 1 ][ 1 ][ 0 ] = 0;
for( int j = 2; j <= num; j ++ ) dp[ 1 ][ j ][ 0 ] = 1;
for( int x = 2; x <= N; x ++ )
{
for( int y = 1; y <= num; y ++ )
{
int val = 1;
if (y == B[ x ] ) val = 0;
for (int k = 0; k <= x; k++)
{
dp[ x ][ y ][ k ] = x;
for( int z = 1; z <= num; z ++ )
{
{
if (k == 0)
{
if( y == z ) dp[ x ][ y ][ k ] = min( dp[ x ][ y ][ k ], dp[ x - 1 ][ z ][ k ] + val );
continue;
}
else if( k == x )
{
if( y != z ) dp[ x ][ y ][ k ] = min( dp[ x ][ y ][ k ], dp[ x - 1 ][ z ][ x - 1 ] + val );
continue;
}
if( y == z ) dp[ x ][ y ][ k ] = min( dp[ x ][ y ][ k ], dp[ x - 1 ][ z ][ k ] + val );
else dp[ x ][ y ][ k ] = min( dp[ x ][ y ][ k ], dp[ x - 1 ][ z ][ k - 1 ] + val );
}
}
}
}
}
int goal = 101;
for( int y = 1; y <= num; y ++ )
for( int z = 0; z <= K; z ++ )
{
goal = min( goal, dp[ N ][ y ][ z ] );
}
cout << "Case #" << i <<": " << goal << endl;
}
return 0;
}