[2016-2017 ACM-ICPC, South Pacific Regional Contest (SPPC 16)]J Just Terraffic

    题目大意：将n个按升序排列的数字分割为一系列长度为2或3的小段，要求相邻且差<=1000的数必须在同一段，相邻且差>=2000的数不能在同一段，询问是否存在这样的分割方案，有则输出长度为2或3的小段的数量，多组解（分割方案不同但是两种小段的数量相同算同一种解）输出Ambiguous，无解输出Impossible。

    题解：比较显然可以看出来是动态规划，无解的处理很容易，但是多组解的判断比较困难。一种比较好的解决思路是，记f[i][0]和f[i][1]分别表示前i个数分割所称长度为2和3的小段的数量，更新时\[f[i][0]=max(f[i-2][0]+1,f[i-3][0])\]\[f[i][1]=max(f[i-2][1],f[i-3][1]+1)\]，这样一来如果有多种解的话，\(2f[n][0]+3f[n][1]\)肯定是大于n的。

    无解的判断另开一个数组g记录即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;

long long f[maxn];
int g[maxn];
int t[maxn];
int n;

bool Check(int l,int r)
{
	for (int i=l;i<r;i++) if (t[i+1]-t[i]>=2000) return false;
	if (t[l]-t[l-1]<=1000) return false;
	if (t[r+1]-t[r]<=1000) return false;
	return true;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	t[0]=t[1]-2000;t[n+1]=t[n]+2000;
	g[0]=1;
	for (int i=2;i<=n;i++)
	{
		if (Check(i-1,i) && g[i-2]) f[i]=f[i-2]+1,g[i]=1;
		if (i>2 && Check(i-2,i) && g[i-3])
			f[i]=max(f[i]/n,f[i-3]/n+1)*n+max(f[i]%n,f[i-3]%n),g[i]=1;
	}
	if (g[n]==0) printf("Impossible\n");
	else if (2*(f[n]%n)+3*(f[n]/n)>n) printf("Ambiguous\n");
	else printf("Cars without trailers: %lld\nCars with trailers: %lld\n",f[n]%n,f[n]/n);
	return 0;
}