Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.

From the window in your room, you see the sequence of n hills, where i-th of them has height ai. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on hills with heights 5 and 6 only.

The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build k houses, so there must be at least k hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?

However, the exact value of k is not yet determined, so could you please calculate answers for all k in range ? Here denotes n divided by two, rounded up.

链接🔗
CF1012C Hills

原题链接🔗 CodeForces 1012C

题意

你有一个由 n(n5000)n (n \le 5000) 个数组成的数组,你一次操作可以把某一个数减一(可以减为负数),如果一个数严格大于它旁边的两个数第一个数只用严格大于第二个数,第 nn 个数只用严格大于第 n1n-1 个数),则称其为优秀的数。现在你想知道,使数组存在至少 kk 个优秀的数最小需要操作几次。,请输出 k[1,n2]k \in [1, \left \lceil \dfrac{n}{2} \right \rceil] 时的答案。

  • 样例输入1
5
1 1 1 1 1
  • 样例输出1
1 2 2

k=1k = 1 时,我们只需要一步,将位置22,或位置44上的数减少11,则会变成[1,0,1,1,1][1,0,1,1,1][1,1,1,0,1][1,1,1,0,1] ,这样位置11 或位置55就会成为优秀的数

k=2,3k = 2 , 3 时,将序列变成 [1,0,1,0,1][1,0,1,0,1],花费为22,位置1,3,51 , 3 , 5是优秀的数

题解

在这一题中,每次改动值,都会对该点的左右两边产生影响,如果只贪心的使每一次新加入的点代价最低,是无法满足正确性的。因此我们考虑使用动态规划算法。

因为我们需要输出kk1n/21-n/2 时优秀的数,所以在dp过程中,其中一维肯定需要记录不同的kk

我们可以设 dp[i][j]dp[i][j] 为前 ii 个数中,(这是不需要考虑jjj+1j+1位置之间的关系),产生 jj 个优秀的数最小修改次数。但在考虑转移过程中,会因为第i1i-1是否为优秀的数,而无法进行转移。

dpdp过程中,如果推不出转移公式,那么有可能是状态方程列错了。

在这题中,我们可以多引入一维,来记录第 ii 位与第 i1i-1 位的情况,定义如下:

  1. dp[i][j][0]dp[i][j][0]ii 个数产生 jj 个优秀数,第 iii1i-1 都不是优秀的最少修改次数
  2. dp[i][j][1]dp[i][j][1]ii 个数产生 jj 个优秀数,第 ii 个是优秀的最少修改次数
  3. dp[i][j][2]dp[i][j][2]ii 个数产生 jj 个优秀数,第 i1i-1 个不是优秀的最少修改次数

稍加思考,我们能得到该转移公式

  • ii 位与第 i1i-1 都不是优秀数,那么只有dp[i1][j][0]dp[i-1][j][0]dp[i1][j][2]dp[i-1][j][2] 的最后一位位不优秀的数

dp[i][j][0]=min(dp[i1][j][0],dp[i1][j][2])dp[i][j][0] = min(dp[i-1][j][0],dp[i-1][j][2])

  • 对于这种情况,我们仅需将 a[i]<a[i1]a[i] < a[i-1] 即可

dp[i][j][2]=dp[i][j][1]+max(0,a[i]a[i1]+1)dp[i][j][2] = dp[i][j][1]+max(0,a[i]-a[i-1]+1)

  • 转移到该步只有两种情况,到数一位不为优秀的数,因为无法出现两个相邻的优秀的数
  1. 考虑从 dp[i1][j1][0]dp[i-1][j-1][0] 转移,我们仅需将 a[i]>a[i1]a[i] > a[i-1] 即可
  2. 考虑从 dp[i1][j1][2]dp[i-1][j-1][2] 转移,在此之前,a[i1]>a[i2]a[i-1] > a[i-2] 的,因此要将 a[i1]a[i-1]a[i2]1a[i-2] - 1 取一个最小值

dp[i][j][1]=min(dp[i1][j1][0]+max(0,a[i1]a[i]+1),dp[i1][j1][2]+max(0,min(a[i1],a[i2]1)a[i]+1))dp[i][j][1] = min(dp[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[i-1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1))

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 2500+10;
int n,m,dp[maxd][3],arr[maxd*2];
int main()
{
    scanf("%d",&n); 
  	m = (n+1) >> 1; // 最多只能产生 (n+1)>>1 严格大于两边的店 
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    for(int i=m;i>=0;i--)
        for(int j=0;j<=2;j++)
            dp[i][j] = 0x3fffffff;
    dp[0][0] = dp[1][1] = 0;
    for(int i=2;i<=n;i++)
        for(int j=m;j>=1;j--)
        {
            dp[j][0] = min(dp[j][0],dp[j][2]);
            dp[j][2] = dp[j][1] + max(0,arr[i]-arr[i-1]+1);
            dp[j][1] = min(dp[j-1][0]+max(0,arr[i-1]-arr[i]+1),dp[j-1][2]+max(0,min(arr[i-1],arr[i-2]-1)-arr[i]+1));
        }
    for(int i=1;i<=m;i++)
        printf("%d ",min(dp[i][0],min(dp[i][1],dp[i][2])));
    return 0;
}