需要做网站的企业,山西手机响应式网站建设,四川移动端网站建设,福田商城网站建设哪家便宜3288 积木大赛 #xff08;2013年NOIP全国联赛提高组#xff09;
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond
题目描述 Description
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦#xff0c;大厦可以看成由 n 块宽…3288 积木大赛 2013年NOIP全国联赛提高组
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond
题目描述 Description
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦大厦可以看成由 n 块宽度为1的积木组成第i块积木的最终高度需要是hi。 在搭建开始之前没有任何积木可以看成 n 块高度为 0 的积木。接下来每次操作小朋友们可以选择一段连续区间[L,R]然后将第 L 块到第 R 块之间含第 L 块和第 R 块所有积木的高度分别增加1。 小 M 是个聪明的小朋友她很快想出了建造大厦的最佳策略使得建造所需的操作次数最少。但她不是一个勤于动手的孩子所以想请你帮忙实现这个策略并求出最少的操作次数。
输入描述 Input Description 输入包含两行第一行包含一个整数 n表示大厦的宽度。 第二行包含 n 个整数第i个整数为hi。 样例输入 Sample Input 5 2 3 4 1 2
样例输出 Sample Output 5
数据范围及提示 Data Size Hint 其中一种可行的最佳方案,依次选择 [1,5] [1,3] [2,3] [3,3] [5,5] 对于 30%的数据有1 ≤ n ≤ 10; 对于 70%的数据有1 ≤ n ≤ 1000; 对于 100%的数据有1 ≤ n ≤ 1000000 ≤ hi ≤ 10000。
这道题大致有两种算法
差分法思考法
本题很明显的告诉我们可以用差分来做小朋友们可以选择一段连续区间[L,R]然后将第 L 块到第 R 块之间含第 L 块和第 R 块所有积木的高度分别增加1下面附上代码。
#include bits/stdc.h
using namespace std;
int a[100001],cf[1000],n;
int main()
{int count0;cinn;for (int i1;in;i){cina[i];}for (int i1;in;i) //求差分数组 {c[i]a[i]; //codevs测试点2是极限情况100000若把c[1]a[1]写在外面会超时我也不知道为啥. cf[i]a[i]-a[i-1];}for (int i1;in;i){while (cf[i]!0) //过滤已完成的值 {int rightn1,j,sum0;for (ji;jn;j){sumcf[j];if (sum0){rightj;break;}}if (rightn1) //如果right的值为n1说明整个数组都进行了加和操作因此只对i进行反向差分. {cf[i]--; //反过程 count;}else{cf[i]--; //反过程 cf[right];count;}}}printf(%d,count);return 0;
}下面是参考别人的思路仔细想想确实很巧妙于是就加进来了。
#include bits/stdc.h
using namespace std;
int a[100001],n;
int main()
{int count0;cinn;for (int i1;in;i){cina[i];}counta[1];for (int i1;in;i){if (a[i]a[i1]){counta[i1]-a[i];}}printf(%d,count);return 0;
}就这几行可以这样来理解。 第一个就是目前的方法数如果后面的项比前面的项要小那么我在进行加1的时候空间选择完全可以覆盖此项最少步数但如果后面的数比前面要大明显的L-R空间选取被打断了不能进行了那么a[i1]项就需要另外的a[i1]-a[i]步来完成。
