第22次CSP第四题

本文主要是介绍第22次CSP第四题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：http://118.190.20.162/view.page?gpid=T125

思路：DP,选择类题目考虑DP
f[i]定义为前i项中种树的种类数目，f[i]=(f[j]*cnt)（0<=j<i,cnt为[j,i)的种类数），由于题目中不允许把树种在已经存在的位置，对于[j,i），j是已经存在的位置，所以往左遍历的时候，[j',i)中的树不能种在j上，即可以通过一个数组st来标记在[j,i)中满足条件的因子k和b(b=j-i，也是不满足的条件)，来防止出现多算了cnt的数目。

思路来自acwing讲解

代码：

#include<bits/stdc++.h>

using namespace std;
const int N=1010,M=100010,mod=(int)1e9+7;
int a[N],f[N];
bool st[M];
vector<int> ve[M];
int main (){
    ios::sync_with_stdio(false);
    for(int i=1;i<M;i++)
        for(int j=i*2;j<M;j+=i)
            ve[j].push_back(i);
    int n;
    cin>>n;
    f[0]=1;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        memset(st,0,sizeof st);
        for(int j=i-1;j>=0;j--){
            int b=a[i]-a[j];
            int cnt=0;
            for(int k:ve[b]){
                if(!st[k]){
                    cnt++;
                    st[k]=true;
                }
            }
            st[b]=true;//
            f[i]=(f[i]+1LL*cnt*f[j]%mod)%mod;
        }
                    
    }
    cout<<f[n-1];


    return 0;
}

这篇关于第22次CSP第四题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！