【Codeforces 659G】Fence Divercity

  如果考虑切去的部分的话，由于切去部分的形状比较复杂，统计起来比较困难，而切去后剩下的部分形状是很清楚的，所以考虑切去后的剩下部分。

  设\(ans_{i,j}\)表示切去从第i列到第j列围栏顶端的块的方案数，显然\[ans_{i,j} = \prod_{k=i+1}^{j-1} {min(h_{k-1},h_k,h_{k+1})} \cdot min(h_i,h_{i+1}) \cdot min(h_{j-1},h_j))\]

  从\(ans_{i,j}\)推到\(ans_{i,j+1}\)，得\[ans_{i,j+1}=ans_{i,j} \cdot \frac{min(h_j,h_{j+1})}{min(h_j,h_{j-1})} \cdot min(h_{j-1},h_j,h_{j+1})\]

  容易发现，向右拓展时答案不受该位置左边距离2以上的数影响。

  设\[sum_i = \sum_{j=1}^{i-1}{ans_{j,i}}\]

  然后

  显然然后\(O(n)\)一遍扫过去就好了，中途把答案加上去。

  这么做是需要用到乘法逆元的，但事实上这里并不需要。

  设\[c_i=\frac{sum_i}{\min\{h_i,h_{i-1}\}}\]

  那么就有\[c_i=c_{i-1} \cdot \min\{h_{i-2},h_{i-1},h_i\} + \min\{h_{i-1},h_i\} \]

  然后还是\(O(n)\)扫一遍，统计答案就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000010,p=1e9+7;

LL h[maxn];
int n;
LL sum,ans;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%I64d",&h[i]),h[i]--;
	if (n==1) {printf("%d\n",h[1]);return 0;}
	sum=min(h[1],h[2])%p;
	ans=(h[1]+h[2]+sum*sum)%p;
	for (int i=3;i<=n;i++)
	{
		LL x=min(h[i-1],h[i]);
		sum=(sum*min(h[i-2],x)%p+x)%p;
		ans=(ans+sum*x+h[i])%p;
	}
	printf("%I64d\n",ans);
	return 0;
}