题目链接 一道DP与基本数学结合的题目。
可以想到有一种dp方式即f[i]表示前i个障碍物的方案数。转移方程: [i] = f[j] * calc (j,i)，calc即在障碍j与障碍i之间分段摆东西。之后设d = a[i] - a[j] 那么就在d中间取约数。算法瓶颈在于calc,这样比较暴力，若是我们枚举j时由i-1枚举到1，每当我们找到一个答案ans,把他加入到一个集合中，在该集合中的数在之后的枚举中便不再能当做答案，否则他一定撞到j这个障碍。倒着枚举每次约数由小至大，可以大幅度剪枝。 注意每个数的约数可以预先筛好。
点击查看代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<bitset>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
const int mod = 1e9+7;
int ad(int x,int y) {
x+=y; return x>=mod?x-mod:x;
}
int mu(int x,int y) {
return 1ll*x*y%mod;
}
set<int>se;
int n;
int a[1005],f[1005];
vector<int>ve[100005];
int calc(int x,int y) {
int d = a[y] - a[x];
se.insert(d);
int s = ve[d].size(),ans=0;
for(int i=0;i<s;i++) {
int o = ve[d][i];
if(se.find(o)!=se.end()) continue;
se.insert(ve[d][i]);
ans++;
}
return ans;
} // calc j-->i
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=1;i<=a[n]/2;i++) {
for(int j=i*2;j<=a[n];j+=i) {
ve[j].push_back(i);
}
}
f[1] = 1;
for(int i=2;i<=n;i++) {
se.clear();
for(int j=i-1;j>=1;j--) {
f[i] = ad(f[i],mu(f[j],calc(j,i)));
}
}
printf("%d",f[n]);
return 0;
}