P1969

题目描述
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为的大厦,大厦可以看成由块宽度为的积木组成,第i块积木的最终高度需要是
在搭建开始之前,没有任何积木(可以看成nn块高度为的积木)。接下来每次操作,小朋友们可以选择一段连续区间,然后将第第块到第 块之间(含第 块和第 块)所有积木的高度分别增加

小MM是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。

题解

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

int main()
{
int n, last = 0, ans = 0;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int a;
cin >> a;
if (a > last)
ans += (a - last);
last = a;
}
cout << ans << endl;
return 0;
}

线段树

↓ 来自 阿尔萨斯’s题解

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

#define ll int

using namespace std;

inline ll read()//快速读入可有可无
{
char c=getchar();
ll s=0,t=1;
while(c<'0'||c>'9')
{
if(c=='-')t*=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*t;
}
ll ans[400004],a[100001],n,answer=0;//a是每个地方需要搭的高
inline ll ls(ll x)//开始线段树,这是返回左子树的节点值,会线段树的不用看了,线段树打发很多
{
return x<<1;
}
inline ll rs(ll x)//右子树
{
return x<<1|1;
}
void build(ll l,ll r,ll s)//递归建树
{
if(l==r)//如果触底就返回
{
ans[s]=l;
return;
}
ll mid=(l+r)>>1;
build(l,mid,ls(s));//二分建树
build(mid+1,r,rs(s));
ll s1,s2;
s1=a[ans[ls(s)]];//列出左右子树中最低处的高
s2=a[ans[rs(s)]];
if(s1<s2)ans[s]=ans[ls(s)];//返回最低处
else ans[s]=ans[rs(s)];
}
ll find(ll s,ll l,ll r,ll xl,ll xr)//注意返回值为位置 ,高度要用a[find(?????)]表示
{
if(xl<=l&&r<=xr)return ans[s];//如果这个节点应该查询,也就是被查询的左右区间包含,就返回
ll mid=(l+r)>>1,lo,lo2,k;
if(xl<=mid)//没错就是这里!一定要注意如果该节点左子树不用查询就直接返回右子树的值,否则再比较
{
lo=find(ls(s),l,mid,xl,xr);//lo就是左子树中最低点的位置
k=lo;//用于比较,记录最低点
if(mid<xr)
{
lo2=find(rs(s),mid+1,r,xl,xr);//lo2是右子树最低点位置
if(a[lo2]<a[lo])k=lo2;//比较
}
}
else//如果没有左子树就直接查询右子树
{
lo=find(rs(s),mid+1,r,xl,xr);
k=lo;
}
return k;
}
void f(ll l,ll r,ll h)//h是之前的高度
{
if(l>r)return;//奇怪的判断,分别判断这个区间是否存在,是否越界*2
if(r<1)return;
if(l>n)return;
ll lo=find(1,1,n,l,r),height;
height=a[lo];
answer+=height-h;//answer加上(当前高度-之前的高度)
f(l,lo-1,height);//二分
f(lo+1,r,height);
}
int main()
{
n=read();
for(ll i=1;i<=n;i++)a[i]=read();
build(1,n,1);
f(1,n,0);
cout<<answer;
}
-------------本文结束,感谢您的阅读-------------