[ARC120E] 1D Party

思路来源
我们发现一个人会先往左走，再往右走，我们可以发现在两人相遇的时候这两人转向相当于交换，所以我们不再需要考虑转向，只需要考虑一个人走过的路程。

然后可以在此基础上发现，一个人往左一个人往右，这两个路程的图像与坐标轴会形成一个三角形，并且如果这个三角形在中间，那么就必须要与另外一个三角形有交，并且只要有交这个三角形就会合法。
那么显然我们只需要从最靠近的三角形转移即可。
记 \(dp_i\) 表示没选第 \(i-1\) 位，以第 \(i\) 位为最后一个三角形右端点的答案，至此问题解决，显然只需要从 \(i-2\) 或 \(i – 3\) 转移 （四个点的三角形拆成两个显然更优）。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e6 + 10;
int n, a[N], dp[N];

int main(){
	//FO("");
	read(n);
	U(i, 1, n) read(a[i]);
	memset(dp, 0x3f, sizeof dp);
	dp[0] = dp[1] = 0, dp[2] = a[2] - a[1], a[n + 1] = a[n]; a[0] = a[1];
	U(i, 3, n + 1)
		D(j, i - 2, max(1, i - 3))
			chkmin(dp[i], max(dp[j], a[i] - a[j - 1]));
	writeln(dp[n + 1] / 2);
	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16880224.html