21 Days Training // Day 14

T1. brick

2 Conclusions :

1. The height of the first and the last brick is 0.
2. For brick i and i+1, abs(h[i+1]-h[i]) cannot be greater than 1.

Proof :
For statement 1, since the region of every operation [L, R], L>=2, R<=N-1, So the height of brick 1 and N do not change.

For statement 2, suppose that we want to change the height of i. So we need to select a region [L, R], and the height of the brick in this region is equal.
To maximize abs(h[i+1]-h[i]), we need to select region [i-1, i+1], or the height of i+1 will also change.
However, after this operation, the region [i-1, i+1] do not satisfy the condition so it cannot be selected again. Also, any other regions that includes [i-1, i+1] cannot be selected.
To make this region be able to be chose, we need th=o change the height of i-1, i+1, but now the abs(h[i+1]-h[i]) will change to 0.

To sum up, abs(h[i+1]-h[i]) cannot be greater than 2.

So, using these 2 conclusions, we can first compute the planss count of a region, and use the multiple principle to get the final result.

In detail, suppose we know the region [L, R] are all -1 except leftmost brick and rightmost brick.
For brick L+1, its height can be h[L], h[L]+1, h[L]-1 .
So the plans count of this point is dp[L+1][h[L]]+dp[L+1][h[L]+1]+dp[L+1][h[L]-1] .
Here, dp[pos][h] shows the plan count when we know the height of the region [L, pos] and the height of pos is h.
Based on this formula, we can get the target value : dp[R][h[R]] .
Specially, when h is 0, current lowest value, dp[pos][h]=dp[pos-1][h]+dp[pos-1][h+1] , and when h is current highest value, dp[pos][h]=dp[pos-1][h]+dp[pos-1][h-1] .

Complexity : O(n^2) .

Code :

#include <bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;

int main() {
    freopen("brick.in", "r", stdin);
    freopen("brick.out", "w", stdout);
    int N;cin >> N;
    int A[N];
    for (int i=0;i<N;i++) cin >> A[i];
    if (N==1) {
        cout <<(A[0]==0||A[0]==-1?"1":"0");
        exit(0);
    }
    if (N==2) {
        cout <<((A[0]==0||A[0]==-1)&&(A[1]==0||A[1]==-1)?"1":"0");
        exit(0);
    }
    A[0] = A[N-1] = 0;
    vector<pair<int, int> > seg;
    int Lx=-1;
    for (int i=0;i<N;i++) {
        if (A[i]==-1) {
            if (Lx==-1) Lx=i;
        }
        else {
            if (Lx!=-1) {
                seg.push_back(make_pair(Lx, i-1));
                Lx=-1;
            }
        }
    }
    if (seg.empty()) {
        for (int i=1;i<N;i++) {
            if (abs(A[i]-A[i-1])>1) {
                cout << 0;
                exit(0);
            }
        }
    }
    long long px=1;
    for (int i=0;i<seg.size();i++) {
        int L=seg[i].first-1, R=seg[i].second+1;
        if (abs(A[R]-A[L])>R-L) {
            cout << 0;
            exit(0);
        }
        // P_+ + P_0 + P_- = R-L
        // P_+ - P_-       = A[R]-A[L]
        long long dp[R-L+1][A[L]+R-L+1];
        dp[0][A[L]]=1;
        for (int i=1;i<=R-L;i++) {
            if (i==1) {
                if (A[L]>0) dp[i][A[L]-1]=1;
                dp[i][A[L]] = dp[i][A[L]+1] = 1;
            }
            else {
                for (int j=A[L]-i;j<=A[L]+i;j++) {
                    if (j<0) continue;
                    if (j==A[L]-i||j==A[L]+i) dp[i][j]=1;
                    else if (j==0||j==A[L]-i+1) dp[i][j] = dp[i-1][j] + dp[i-1][j+1];
                    else if (j==A[L]+i-1) dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                    else dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1];
                    dp[i][j] %= MOD;
                }
            }
        }
        px*=dp[R-L][A[R]];
        px%=MOD;
    }
    cout << px;
    return 0;
}