CF1012C Hills

CF1012C Hills

题目描述

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 $a_i$ . 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 $1\le k\le \lceil \frac{n}{2}\rceil$? Here $\lceil \frac{n}{2}\rceil$ denotes $n$ divided by two, rounded up.

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

一行 $\lceil \frac{n}{2}\rceil$ 个数，第 $i$ 个数代表 $k=i$ 时的答案

样例1

样例输入1

5
1 1 1 1 1
1
2

样例输出1

1 2 2
1

样例2

样例输入2

3
1 2 3
1
2

样例输出2

0 2
1

样例3

样例输入3

5
1 2 3 2 2
1
2

样例输出3

0 1 3
1

数据范围

$1\le n\le 5000$

$1\le ai\le 100000$

题目大意

给你$n$个数，你一次操作可以把某一个数减一（可以减为负数），你的目标是使任意的$k$个数严格大于它旁边的两个数（第一个数只用严格大于第二个数，第$n$个数只用严格大于第$n-1$个数），问最少需要几次操作。$k$是不确定的，请输出 $k\in [1,\lceil \frac{n}{2}\rceil ]$ 时的答案。

题解

设$f_{i,j}$表示前$i$个中有$j$个被选中，且第$i$个被选中所需的最小时间。则状态转移式为：

$f_{i,j}=\min (\underset{k=1}{\overset{i-2}{\min }}{f}_{k,j-1}+w_{i-1,i},f_{i-2,j-1}+\max (w_{i-1,i},w_{i,i+1}))$

其中$w_{i,j}$表示将$a_i$的高度减少至$a_i<a_j$，显然$w_{i,j}=\max (0,a_i-a_j+1)$。不需要预处理，用的时候直接求即可。

当然，如果这样做，时间复杂度为$O(n^3)$，会TLE，所以我们考虑优化。

可以发现，每次都会用到$\underset{k=1}{\overset{i-2}{\min }}{f}_{k,j-1}+w_{i-1,i}$。所以我们设$g_{i,j}=\underset{k=1}{\overset{i-2}{\min }}{f}_{k,j-1}+w_{i-1,i}$，每次求$f$值时顺便更新$g$值，最后$\underset{j=i}{\overset{n}{\min }}{f}_{j,i}$即为选$i$座山的答案。

code

#include
using namespace std;
int n,a[100005];
long long ans,g[5005],f[5005][2505];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<=n;i++){
		for(int j=1;j<=(n+1)/2;j++) f[i][j]=1e18;
		g[i]=1e18;
	}
	for(int i=1;i<=n;i++){
		f[i][1]=max(0,a[i-1]-a[i]+1)+max(0,a[i+1]-a[i]+1);
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=(i+1)/2;j++){
			f[i][j]=min(g[j-1]+max(0,a[i-1]-a[i]+1),
			f[i-2][j-1]-max(0,a[i-1]-a[i-2]+1)+max(0,a[i-1]-min(a[i],a[i-2])+1))+max(0,a[i+1]-a[i]+1);
		}
		for(int j=1;j<=(i+1)/2;j++){
			g[j]=min(g[j],f[i-2][j]);
		}
	}
	for(int i=1;i<=(n+1)/2;i++){
		ans=1e18;
		for(int j=i;j<=n;j++) ans=min(ans,f[j][i]);
		printf("%lld ",ans);
	}
	return 0;
}
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