Tag:Interval DP
Article From:https://www.cnblogs.com/ljzalc1022/p/9064263.html

A DFS order of traversal of a program below a tree is given

used[1 ... n] = {0, ..., 0};

procedure dfs(v):
    print v;
    used[v] = 1;
    for i = 1, 2, ..., n:
        if (a[v][i] == 1 and used[i] == 0):
            dfs(i);

dfs(1);

Ask the number of trees that can get the sequence

It is observed that the same subtree is located in the adjacent area, and the root of the subtree is the first element in the interval, and the solution of dp[l][r] is interval [l and r].
\[dp[l][r]=\sum_{i\in[l,r],i!=r||b[i+1]>b[l]} dp[l+1][i]*dp[i+1][r]\]

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int n, b[505];
int f[505][505];
void ModAdd(int & x, int y) {
    x += y;
    if(x >= mod) x-= mod;
}
int DP(int l, int r) {
//  cerr << l << ' ' << r << endl;
    if(l >= r) return 1;
    int & res = f[l][r];
    if(res != -1) return res;
    res = 0;
    for(int i = l; i <= r; i++) {
        if(i != r && b[i + 1] <= b[l]) continue;
        ModAdd(res, (long long)DP(l + 1, i) * DP(i + 1, r) % mod);
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    memset(f, -1, sizeof(f));
    printf("%d\n", DP(2, n));
    return 0;
}
Link of this Article: CodeForces509F Progress Monitoring

Leave a Reply

Your email address will not be published. Required fields are marked *