$\quad$艹!垃圾DP真的是写的时候怎么都想不到 , 一听分析就秒懂
$\quad$$\quad$重中之重, 设DP方程的时候不知道开几维, 就从第一维开, 不够再加
$\quad$$\quad$此题的状态转移方程只需一维
$\quad$$\quad$设$f[i]$为用了前i个障碍点的所有方案, 来做状态划分
$\quad$$\quad$设$j$为从$0-i$的每个间断点
$\quad$$\quad$则
$\quad$$\quad$$\quad$$f[i]=(f[0]\*cnt1+f[1]\*cnt2+…+f[j]\*cnt3+…+f[i-1]\*cnt(i-1))$
$\quad$$\quad$首先我们知道$f[0],f[1],....f[i-1]$已经在之前的拓扑序计算中得到了具体值, 那重点就在求cnt数组
$\quad$$\quad$cnt数组不是一成不变的, 他牵扯到$i$和$j$的选值
$\quad$$\quad$我们要求的是$a[i]-a[j]$对应的cnt值, 还要减去重复计数
$\quad$$\quad$处理一下约数数组cnt后, 对每次循环遍历每个对应的约数数组cnt求去掉重复计数后的数量
$\quad$$\quad$开一个布尔数组记录一下当前循环已经用过了哪些约数即可
#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=2e5+10,mod=1e9+7;
vector<int> cnt[M];
int n;
int a[N];
int f[N];
bool st[M];
void init(){ ///处理约数数组cnt
for(int i=1;i<M;i++){
for(int j=2*i;j<M;j+=i){
cnt[j].push_back(i);
}
}
}
int main(){
scanf("%d", &n);
for (int i = 0; i <n; i ++ ) scanf("%d",&a[i]);
init();
f[0]=1;
for(int i=1;i<n;i++){
memset(st,0,sizeof st);
for(int j=i-1;j>=0;j--){
int k=a[i]-a[j];
int num=0;
for(auto x:cnt[k]){
if(st[x]) continue;
st[x]=true;
num++;
}
st[k]=true;
f[i]=(f[i]+(long long)f[j]*num)%mod;
}
}
cout<<f[n-1];
return 0;
}
另,精简了一下内存,现在稍微快一点,能到100ms之内了
请问大佬 为啥每次都要把用过的约数都设置成true
如果使用过,说明这个间隔的距离在某一个距离上踩到了左边界障碍物上,然后我们对左边界障碍物从右向左遍历,如果某个间隔碰到了靠右的左边界障碍物,那么肯定没法往左边用了。
谢谢谢
确实。老哥写的很好,有个地方我给大家踩个坑
f[i]=(f[i]+(long long)f[j]*num)%mod;
这一行要是不加 long long,如果加成了long都过不了(我指csp的那个比较严格的测评系统,只能过30%),但是在acwing上就可以过。