noip2013提高组 积木大赛解题报告

1．积木大赛  (block.cpp/c/pas)   

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

 小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。

但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。 

 

【输入】   输入文件为block.in 

 输入包含两行，第一行包含一个整数

第二行包含

�个整数，第�个整数为ℎ�。 

【输出】    输出文件为block.out    仅一行，即建造所需的最少操作数。    【输入输出样例】  block.in   5 

2 3 4 1 2 

block.out  5    【样例解释】    其中一种可行的最佳方案，依次选择    [1,5]    [1,3]    [2,3]    [3,3]    [5,5]    【数据范围】    对于30%的数据，有1 ≤ n ≤ 10;� ≤ 10；    对于70%的数据，有1 ≤ n ≤ 1,000;� ≤ 1000； 

  对于100%的数据，有1 ≤ n ≤ 100,000, 1 ≤ h[i]�  ≤ 10,000� 

 

暴搜很容易超时，这题用栈的思想；

从头开始读入，2->3->4->1->2

当后面比前面大的时候不需任何处理，因为后面的大的处理时会包括了前面小的

直到进栈 1 时，前面是 4 

说明 全部都可以垒1层 ， 且垒完一层后 1 层可以在垒 3 层就可以垒完；

注意：到了最后一个后面没有了，就把它出栈；

参考程序：

#include<iostream> #include<cstdio> using namespace std; int main() { int a[100001]; int max1=0; int s; int i; scanf("%d",&s); for(i=1;i<=s;i++) { scanf("%d",&a[i]); } for(i=2;i<=s;i++) if(a[i]<a[i-1]) max1+=a[i-1]-a[i]; printf("%d",max1+a[s]);//最后一个出栈 return 0; }