题解：CF659G Fence Divercity

· · 题解

非常简单啊，一想就想到了，根本不知道这题为什么能是紫题

这题我们考虑 dp。

首先易知删除区域为连通块，然后分四种情况：

  1. 不与前连，不与后连。则共有删 1 个，删 2 个，……，删 a_i-1 个共 a_i-1 种情况。
  2. 与前连，不与后连。如果 a_{i-1}<a_i 则不能删 1 个，……，删 a_i-a_{i-1} 个，即 a_{i-1}-1 种情况；如果 a_{i-1}\ge a_i 则同第一种， 共有 a_i-1 种情况；综合起来，有 \min(a_{i-1},a_i)-1 种情况。而且，由于乘法原理，情况还要乘上一个 dp_{i-1}，所以最后一共有 (\min(a_{i-1},a_i)-1)\times dp_{i-1} 种情况。
  3. 不与前连，与后连。如果 a_{i+1}<a_i 则不能删 1 个，……，删 a_i-a_{i+1} 个，即 a_{i+1}-1 种情况；如果 a_{i+1}\ge a_i 则同第一种， 共有 a_i-1 种情况；综合起来，有 \min(a_{i+1},a_i)-1 种情况。
  4. 与前连，与后连。类似地，可知共有 (\min(a_{i-1},a_i,a_{i+1})-1)\times dp_{i-1} 种情况。

前两种直接累加到 ans 中，后两种累加到 dp_i。

这不会越界。一方面，因为 dp_0 的初始值为 0，零乘任何数都得零，所以不用担心；另一方面， dp_n 可能会用到 a_{n+1}，但是 dp_n 就是非法情况（n 后面无木板与它连），可以不管，只要不把数组大小卡死在 n 即可。

接下来是代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],dp[1000005],ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        dp[i]=(min(a[i],a[i+1])-1+(min(a[i],min(a[i-1],a[i+1]))-1)*dp[i-1])%1000000007;
        ans+=a[i]-1+(min(a[i],a[i-1])-1)*dp[i-1];
        ans%=1000000007;
    }
    cout<<ans;
}