首页 > 代码库 > [noip2013 d2t1]积木大赛

[noip2013 d2t1]积木大赛

题意:给定一串目标数,初始每个位置上的值均为0,每次操作可以给某段连续区间上的每个数字加一,求最少操作数

朴素暴力可以期望70~80的分数

简单分析可以得出对于每个目标数,若小于前面的数,则对答案无贡献,否则将其与前一个数的差值加入答案即可

然而我还是想了半天QAQ

技术分享
 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n;
 5 int last,now;
 6 int cnt=0;
 7 int main(){
 8     scanf("%d",&n);
 9     last=0;
10     for (int i=1;i<=n;i++){
11         scanf("%d",&now);
12         if (now>last) cnt+=now-last;
13         last=now;
14     }
15     printf("%d\n",cnt);
16     return 0;
17 }
View Code

 

[noip2013 d2t1]积木大赛