Analysis: Poker Hands by Richard Peng

Several solutions are possible, such as repeatedly removing the longest straight possible. However, the simplest is probably via. the observation that the minimum number of hands equals to half the sum of differences between adjacent values of a_i (assuming that values outside of the interval 1..n are 0).

We first show that this value is a lower bound on the answer. Each hand only changes the difference between values on its endpoints, which is two entries. For the other direction, consider removing the longest straight possible. Let this straight be i...j, then we have a_i > 0, a_{i - 1} = 0, which means playing it decreases |a_i - a_{i - 1}| by 1. A similar claim also holds for j and j + 1. Therefore such a sequence of moves exist, and as a corollary we also show the optimality of the greedy algorithm that always plays the longest straight.

/*
LANG: C++
*/

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100100;

int n;
int a[MAXN];

int main() {
freopen("poker.in", "r", stdin);
freopen("poker.out", "w", stdout);
  scanf("%d", &n);
  a[0] = a[n + 1] = 0;
  for(int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  ll ans = 0;
  for(int i = 0; i <= n; ++i) {
    ans += ll(abs(a[i + 1] - a[i]));
  }
  ans /= 2LL;
  printf("%lld\n", ans);
  return 0;
}