题解：AT_agc026_d [AGC026D] Histogram Coloring

· · 题解

Solution

简单 DP 题。

按理说，我们确定了最下面那一行的情况，其他行几乎就是确定的了。

但是很容易发现，只考虑相邻两数的和，序列 010101 和 101010 是不做区分的。

因此我们需要设两个量，分别表示最底端是 01 交错的方案数和不是 01 交错的方案数。（方便起见，01 交错的方案数只算一半）。用二元组 (x,y) 表示。

考虑每次找到最矮的数（可能有多个）他们将序列划分成若干个连续段。

我们有两种操作：

  1. 将一段区间下面扩展一行。(x,y) \to (2x,y)。
  2. 将若干段区间合并。\to (\prod x,\prod (2x+y) - 2 \prod x)。

直接暴力可以做到 O(n^2)。使用笛卡尔树优化可以做到 O(n \log n)。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100+10,MOD=1e9+7;
int n,h[MAXN];
int qpow(int base,int p) {
    int ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
pair<int,int> solve(int l,int r,int ot) {
    int mn=*min_element(h+l,h+r+1),lst=l-1;
    vector<pair<int,int>> vc;
    ffor(i,l,r) if(h[i]==mn) {
        if(lst+1<=i-1) {
            auto pr=solve(lst+1,i-1,mn);
            vc.push_back({pr.first*2%MOD,pr.second});
        }
        lst=i,vc.push_back({1,0});
    }
    if(lst+1<=r) {
        auto pr=solve(lst+1,r,mn);
        vc.push_back({pr.first*2%MOD,pr.second});   
    }
    int al=1,fst=1;
    for(auto pr:vc) al=(2*pr.first+pr.second)%MOD*al%MOD,fst=fst*pr.first%MOD;
    return {fst*qpow(2,mn-(ot+1))%MOD,(al-2*fst)%MOD};
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>h[i];
    auto pr=solve(1,n,0);
    cout<<((pr.first*2+pr.second)%MOD+MOD)%MOD;
    return 0;
}