题目传送门：Link。
算法：DP。
设计状态
第一眼看着道题就感觉像是 DP，再观察数据范围大概是 \(O(n^2)\) 的时间复杂度。
因为要求多个 \(k\) 的答案，那么状态第一维显然是令多少个数满足条件，第二位就是算到第几个数。
- \(dp_{i,j,0}\) 表示前 \(i\) 个数有 \(j\) 个满足条件，\(i\) 和 \(i-1\) 都不满足条件的最少操作数。
- \(dp_{i,j,1}\) 表示前 \(i\) 个数有 \(j\) 个满足条件，\(i\) 满足条件的最少操作数。
- \(dp_{i,j,2}\) 表示前 \(i\) 个数有 \(j\) 个满足条件，\(i-1\) 满足条件的最少操作数。
注：此处不记对 \(i+1\) 的影响。
转移方程
\[\begin{split} dp_{i,j,0}=\min{(dp_{i-1,j,0},dp_{i-1,j,2})}&\qquad (1)\\ dp_{i,j,2}=dp_{i-1,j,1}+\max{(0,a_i-a_{i-1}+1)}&\qquad (2)\\ dp_{i,j,1}=\min{(dp_{i-1,j-1,0}+\max{(0,a_i-a_{i-1}+1)},dp_{i-1,j-1,2}+\max{(0,\min{(a_{i-1},a_{i-2}-1)}-a_i+1)})}&\qquad (3)\\ \end{split} \]\((1)\) 式和 \((2)\) 式显然。
对于 \((3)\) 式我们分类讨论：
-
前两个都不满足条件，那么 \(i-1\) 一定是原来的数，即没有被操作过，需要的操作数就是 \(\max{(0,a_{i-1}-a_i+1)}\)。
-
\(i-2\) 满足条件，那么 \(i-1\) 已经变成了 \(\min{(a_{i-1},a_{i-2}-1)}\)，还需要的操作数就是 \(\max{(0,\min{(a_{i-1},a_{i-2}-1)}-a_i+1)}\)。
滚动数组
第一维显然可以消去，因此我们使用滚动数组优化。
注意转移只用到了 \(dp_{i-1,j}\) 和 \(dp_{i-1,j-1}\)，故我们逆序枚举 \(j\)。
此外考虑同 \(i,j\) 时状态之间的互相影响，要用 0,2,1 的顺序更新第三维。
/*
* Title: 1012C. Hills
* Source: CF
* URL: https://codeforces.com/problemset/problem/1012/C
* Author: Steven_lzx
* Command: -std=c++23 -Wall -fno-ms-extensions
* Date: 2022.10.20
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,dp[2510][3],a[5010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=(n+1)>>1;~i;i--)
for(int j=0;j<=2;j++)
dp[i][j]=0x3fffffff;//将不存在的状态设为 INF，INF 不能太大防止爆 int
dp[0][0]=dp[1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=(i+1)>>1;j;j--)//滚动数组
{
dp[j][0]=min(dp[j][0],dp[j][2]);
dp[j][2]=dp[j][1]+max(0,a[i]-a[i-1]+1);
dp[j][1]=min(dp[j-1][0]+max(0,a[i-1]-a[i]+1),dp[j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
}
}
for(int i=1;i<=(n+1)>>1;i++)
{
printf("%d ",min({dp[i][0],dp[i][1],dp[i][2]}));
}
return 0;
}