[noip2013] building block competition [noip2018] road laying greed / difference

In fact, these two questions are the same idea , A positive change , One changes in reverse . So you can traverse the array from front to back , If a[i] > a[i - 1], Just add the difference between them , If a[i] <= a[i - 1],a[i] Can use a[i - 1] To achieve , That is, there is no need to come out more times alone 【 greedy 】. If you look at the difference , That is, the answer is the sum of all positive numbers in the difference array .

Building blocks competition

Original link ： Sign in — major IT Written interview preparation platform _ Cattle from

 

AC Code ：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define PII pair<int,int>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for(int i = n; i >= 1; ++i)

using namespace std;

const double pi = acos(-1.0);

const int N = 1e5 + 10;

int a[N], b[N];

int main()
{
    int n;
    scanf("%d", &n);
    int res = 0;
    rep(i, n) scanf("%d", &a[i]), b[i] = a[i] - a[i - 1];
    for(int i = 1; i <= n; i++)
        if(a[i] > a[i - 1]) res += a[i] - a[i - 1];
    cout << res;
    return 0;
}

Road laying

Sign in — major IT Written interview preparation platform _ Cattle from  

 

AC Code ：

The same way of thinking , You can write it yourself ~