I,J [NOIP2013]积木大赛, [NOIP2018]道路铺设
直接上结论,对 数组差分以后所有正数或所有负数的绝对值即为答案。
my code:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n,ans; int a[maxn]; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); if(a[i] > a[i - 1]) ans += a[i] - a[i - 1]; } printf("%d",ans); return 0; }
std:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1000005; const long long mod = (long long)1e9 + 7; long long d[MAXN], ans; int n; void diff(long long a[]) { for (int i = n; i ; --i) { a[i] = (a[i] - a[i - 1]) % mod; } return; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%lld", &d[i]); } diff(d); for (int i = 1; i <= n; ++i) { ans += max(d[i], 0LL); } printf("%lld\n", ans); return 0; }