[数据结构与算法]CSP：校门外的树

校门外的树

原题链接

涉及知识点：

1. 动态规划

满分代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL; // int会溢出
const int N = 1010;
const int M = 100010;
const int MOD = 1e9 + 7;
int a[N];   // a[i]表示障碍物i坐标
int f[N];   // f[i]表示截至第i个障碍物的方案数
bool s[M];   // s[i]表示是否使用过约数i
vector<int> cnt[M]; // cnt[i]表示i的约数集合

void init() { // 求j的约数集合
    for (int i = 1; i < M; ++i) {
        for (int j = 2 * i; j < M; j += i) {
            cnt[j].push_back(i);
        }
    }
}

int main() {
    init();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    f[0] = 1;
    for (int i = 1; i < n; ++i) {
        memset(s, 0, sizeof(s)); // 每次都要重新赋值
        for (int j = i - 1; j >= 0; --j) {
            int d = a[i] - a[j];
            int num = 0;
            for (int k : cnt[d]) {
                if(s[k]) continue;
                s[k] = true;
                num++;
            }
            s[d] = true; // 区间长度也要标记
            f[i] = (f[i] + LL(f[j]) * num) % MOD;
        }
    }
    printf("%d", f[n - 1]);
    return 0;
}

参考题解