链接：https://codeforces.com/contest/360/problem/B
思路：这个题dp思路就比较巧妙，首先先二分最后的答案，然后令dp[i]表示i是最后一个不同的元素，此时前i个元素相邻的差的绝对值小于二分值时所需要的最小的更改次数，那么转移就是dp[i] = min{dp[j] + i - j - 1} (j < i)。最后找所有的i，看是否存在dp[i] + n - i <= k即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
using namespace std;
const int maxn = 2020;
int dp[maxn];
typedef long long ll;
int n, k;
ll a[maxn];
bool (ll x){
for(int i = 1; i <= n; i++) dp[i] = i - 1;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(abs(a[j] - a[i]) <= 1ll * (j - i) * x){
dp[j] = min(dp[j], dp[i] + j - i - 1);
}
}
if(dp[i] + n - i <= k) return true;
}
return false;
}
int main(){
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
ll lb = 0, ub = 2e9, ans = 0;
while(ub >= lb){
ll mid = ub + lb >> 1;
if(check(mid)){
ub = mid - 1;
ans = mid;
}
else lb = mid + 1;
}
printf("%lldn", ans);
return 0;
}
|
近期评论