神人题解

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

namespace MFlow {
	const int N = 1e5;
	const int M = 2e5;	
	struct Edge {
		int to, w, nxt, ansid;
	} edges [M + 5];
	
	int m, ecnt = 1, head [N + 5], cur [N + 5], dep [N + 5], ans [N + 5];
	void add (int u, int v, int w, int ansid = 0) {
		ecnt ++;
		edges [ecnt] = {v, w, head [u], ansid};
		head [u] = ecnt;
		
		ecnt ++;
		edges [ecnt] = {u, 0, head [v]};
		head [v] = ecnt;
	}
	
	queue <int> q;
	bool bfs (int s, int t) {
		memset (dep, 0, sizeof dep);
		dep [s] = 1;
		while (!q. empty ()) q. pop ();
		q. push (s);
		while (!q. empty ()) {
			int u = q. front (); q. pop ();
			for (int ei = head [u] ; ei ; ei = edges [ei]. nxt) {
				auto &e = edges [ei];
				if (!dep [e. to] && e. w) {
					dep [e. to] = dep [u] + 1;
					q. push (e. to);
					if (e. to == t) return 1;
				}
			}
		}
		return 0;
	}
	
	int dfs (int u, int t, int flow) {
		if (u == t) return flow;
		int sum = 0;
		for (int e = cur [u] ; e ; e = edges [e]. nxt) {
			cur [u] = e;
			int to = edges [e]. to;
			if (edges [e]. w && dep [to] == dep [u] + 1) {
				int f = dfs (to, t, min (flow, edges [e]. w));
				edges [e]. w -= f;
				edges [e ^ 1]. w += f;
				sum += f;
				flow -= f;
				if (!flow) break;
			}
		}
		if (!sum) dep [u] = 0;
		return sum;
	}
	
	int dinic (int s, int t, int n) {
		int flow = 0;
		while (bfs (s, t)) {
			for (int i = 1 ; i <= n ; i ++) cur [i] = head [i];
			flow += dfs (s, t, inf);
		}
		return flow;
	}
	
	int* count_ans () {
		for (int i = 1 ; i <= ecnt ; i ++)  {
			if (edges [i]. ansid) {
				ans [edges [i]. ansid] += edges [i]. w;
			}
		}
		return ans; 
	} 
	
	void clear () {
		ecnt = 1;
		memset (head, 0, sizeof head);
		memset (ans, 0, sizeof ans);
	}
};

using MFlow :: add;
using MFlow :: dinic;
int n, m, ids [105] [105], a [105];
void Turn () {
	cin >> n;
    m = 1;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> a [i];
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= a [i] ; j ++) {
            ids [i] [j] = ++ m;
            add (1, ids [i] [j], 1);
        }
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= a [i] ; j ++) {
            if (ids [i] [j - 1])
                add (ids [i] [j - 1], ids [i] [j], inf);
            if (ids [i - 1] [j])
                add (ids [i - 1] [j], ids [i] [j], inf);
            if (ids [i + 1] [j])
                add (ids [i + 1] [j], ids [i] [j], inf);
        }
    }
    cout << dinic (1, ids [n] [a [n]], m);
}

int _; void Init () {
//	ios :: sync_with_stdio (0); cin. tie (0); cout. tie (0); 
	_ = 1;
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
//	cin >> _;
}

	signed main () { Init ();
	while (_ --> 0)
	Turn (); return 0; }