【Codeforces 653E】Bear and Forgotten Tree 2
【Codeforces 659F】Polycarp and Hay

【Codeforces 659G】Fence Divercity

Zarxdy34 posted @ 2016年4月03日 11:19 in Codeforces with tags DP , 324 阅读

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

  设\(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}}\]

  然后

\[ sum_j=\sum_{i=1}^{j-1}{ans_{i,j}}\]
\[ =\sum_{i=1}^{j-2}{ans_{i,j-1}}\cdot\frac{\min\{h_j,h_{j-1}\}}{\min\{h_{j-1},h_{j-2}\}}\cdot\min\{h_{j-2},h_{j-1},h_j\}+ans_{j-1,j} \]
\[ =sum_{j-1}\cdot\frac{\min\{h_j,h_{j-1}\}}{\min\{h_{j-1},h_{j-2}\}}\cdot\min\{h_{j-2},h_{j-1},h_j\}+(\min\{h_{j-1},h_j\})^2 \]

  显然然后\(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;
}

  


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top