Tehran 2010

Indisputable Right

Aki

大山峰dp,中间的小山峰贪心。

#include <bits/stdc++.h>

using namespace std;

int sgn (int x) { return x < 0 ? -1 : x > 0; }

struct point {
	int x, y;
	explicit point (int x = 0, int y = 0) : x (x), y (y) {}
};

point operator + (const point &a, const point &b) {
	return point (a.x + b.x, a.y + b.y);
}

point operator - (const point &a, const point &b) {
	return point (a.x - b.x, a.y - b.y);
}

point operator * (const point &a, const int &b) {
	return point (a.x * b, a.y * b);
}

point operator / (const point &a, const int &b) {
	return point (a.x / b, a.y / b);
}

double dot (const point &a, const point &b) {
	return a.x * b.x + a.y * b.y;
}

double det (const point &a, const point &b) {
	return a.x * b.y - a.y * b.x;
}

bool operator < (const point &a, const point &b) {
	return a.x < b.x;
}

bool operator == (const point &a, const point &b) {
	return a.x == b.x && a.y == b.y;
}

struct line {
	point s, t;
	line (const point &s = point (), const point &t = point ()) : s (s), t (t) {}
};

bool point_on_segment (const point &a, const line &b) {
	return sgn (det (a - b.s, b.t - b.s)) == 0 && sgn (dot (b.s - a, b.t - a)) <= 0;
}

bool two_side (const point &a, const point &b, const line &c) {
	return sgn (det (a - c.s, c.t - c.s)) * sgn (det (b - c.s, c.t - c.s)) < 0;
}

bool intersect_judgment (const line &a, const line &b) {
	if (point_on_segment (b.s, a) || point_on_segment (b.t, a)) return false;
	if (point_on_segment (a.s, b) || point_on_segment (a.t, b)) return false;
	return two_side (a.s, a.t, b) && two_side (b.s, b.t, a);
}

const int N = 505, INF = 1e9;
point mount[N], poi[N * N];
int pre100[N], pre[N][N][2][2], cost[N], n, m, cnt[N], dp[N][N];
bool seen[N];
vector<int> incave[N * N];
bool see(point a, point b) {
	line ab = line(a, b);
	for (int i = 1; i <= n; ++ i) {
		line L = line(mount[i], point(mount[i].x - mount[i].y, 0));
		line R = line(mount[i], point(mount[i].x + mount[i].y, 0));
		if (intersect_judgment(ab, L) || intersect_judgment(ab, R)) return 0;
	}
	return 1;
}
int solve(vector<point> a, int ul, int ur, int l, int r) {
	if (a.empty()) return 0;
	for (int i = l; i < r; ++ i) cnt[i] = seen[i] = 0;
	if (!ul && !ur) {
		if (a.size() != m) return INF;
		for (point p : a) {
			if (p.y == 50) {
				for (int i : incave[p.x]) seen[i] = 1;
			}
			for (int i : incave[p.x]) cnt[i] ++;
		}
		int res = 0;
		int cnt_cnt = 0;
		for (int i = l; i < r; ++ i) {
			//printf("cave %d cnt = %d seen = %d\n", i, cnt[i], seen[i]);
			cnt_cnt += !!cnt[i];
			if (cnt[i] && !seen[i]) {
				res ++;
				seen[i + 1] = 1;
			}
		}
		if (cnt_cnt == 1) res = 0;
		return res;
	}
	for (point p : a) {
		if (ul && see(mount[l], p)) {
			for (int i : incave[p.x]) {
				seen[i] = 1;
			}
		}
		if (ur && see(mount[r], p)) {
			for (int i : incave[p.x]) seen[i] = 1;
		}
		for (int i : incave[p.x]) cnt[i] ++;
	}
	int res = 0;
	for (int i = l; i < r; ++ i) {
		//printf("cave %d cnt = %d seen = %d\n", i, cnt[i], seen[i]);
		if (cnt[i] && !seen[i]) {
			res ++;
			seen[i + 1] = 1;
		}
	}
	return res;
}
int main() {
	while (scanf("%d%d", &n, &m) == 2 && n + m) {
		int x = 0, las100 = 0;
		mount[0] = point(-100, 100);
		for (int i = 1; i <= n; ++ i) {
			int a;
			scanf("%d", &a);
			mount[i] = point(x + a, a);
			for (int j = max(0, mount[i - 1].x); j <= mount[i].x; ++ j) incave[j].push_back(i - 1);
			x += 2 * a;
			if (a == 100) {
				pre100[i] = las100;
				las100 = i;
			}
		}
		mount[n + 1] = point(x + 100, 100);
		pre100[n + 1] = las100;
		for (int j = max(0, mount[n].x); j <= mount[n + 1].x; ++ j) incave[j].push_back(n);
		for (int i = 1; i <= m; ++ i) {
			int x;
			scanf("%d", &x);
			int id = incave[x][0];
			if (mount[id].x + 100 <= x) id ++;
			if (x < mount[id].x) {
				poi[i] = point(x, mount[id].y - (mount[id].x - x));
			}
			else {
				poi[i] = point(x, mount[id].y - (x - mount[id].x));
			}
		}
		for (int i = 0; i <= n + 1; ++ i) {
			cost[i] = 1;
			for (int j = 1; j <= m; ++ j) if (poi[j].x == mount[i].x) cost[i] = 0;
		}
		for (int r = 1; r <= n + 1; ++ r) {
			if (mount[r].y != 100) continue;
			int l = pre100[r];
			vector<point> all;
			for (int i = 1; i <= m; ++ i) if (mount[l].x < poi[i].x && poi[i].x < mount[r].x) all.push_back(poi[i]);
			for (int ul = 0; ul < 2; ++ ul) {
				for (int ur = 0; ur < 2; ++ ur) {
					pre[l][r][ul][ur] = solve(all, ul, ur, l, r);
					//printf("pre[%d][%d][%d][%d] = %d\n", l, r, ul, ur, pre[l][r][ul][ur]);
				}
			}
		}
		dp[0][0] = 0;
		dp[0][1] = INF;
		for (int i = 1; i <= n + 1; ++ i) {
			if (mount[i].y != 100) continue;
			dp[i][0] = dp[i][1] = INF;
			int j = pre100[i];
			for (int a = 0; a < 2; ++ a) {
				for (int b = 0; b < 2; ++ b) {
					dp[i][b] = min(dp[i][b], dp[j][a] + pre[j][i][a][b] + b * cost[i]);
				}
			}
		}
		printf("%d\n", dp[n + 1][0]);
		for (int i = 0; i <= x + 100; ++ i) incave[i].clear();
	}
}