CSP202104-4 校门外的树

设状态时，首先从简单状态设起：

一维不行再试二维、简单状态应付不了再设复杂的（因为某些状态可以体现在状态转移的过程中，或者说状态转移方程中，不一定体现在原式中）

E.g.

计算机软件能力认证考试系统-校门外的树

我：一开始设状态想的是\(f[i][j][k]\)代表 \(i\) 到 \(j\)，化为 \(k\) 个等差段的方案数

正解：\(f[i]\) 代表前 \(i\)个障碍物的方案总数

同理，DP模型的思考也要由简单到复杂。

我：一开始想的区间DP

正解：线性DP，简单求个和

上面这里想明白了，这题就有60分了，复杂度大概是 \(N^2*logai * ai\) ?

接下来这题有个优化：

我们来看看如何想到这个优化

首先，我们不难发现，主要是每次重新计算\(cnt(i,j)\)的过程十分耗时。如果前面的计算能够为后面答案产生贡献的话，那么会很棒。考虑转换下枚举顺序（其实是经典trick），从大到小枚举\(j\)（即从小到大算\(cnt(i,j)\)）。我们利用一下这题里的一个规律，就可以直接判断一个因子能不能加入答案了。

点击查看代码

ll P = 1e9+7, inf = 0x3f3f3f3f;

const ll Inf = 0x3f3f3f3f3f3f3f3fll; 

int N, M, T, RT, cnt ;

int a[1005]; ll f[1005]; int vis[100005];

ll cal(int d, int id) { //这里是一个小trick，用id来标记判断，就不用每次memsetvis数组了

    ll res = 0;

    for_(i,1,sqrt(d)) {

        if(d % i == 0) {

            if(vis[i] != id) ++res,vis[i] = id;

            if(vis[d/i] != id) ++res,vis[d/i] = id;

            res %= P;

        }

    }

    return (res - 1 + P) % P; // -1 减掉公差为区间长的答案（空区间）

}

int main()

{

    cin >> N;

    for_(i,1,N) cin >> a[i];  

    f[1] = 1;

    for_(i,1,N)

        dwn_(j, i - 1, 1)

            f[i] = (f[j] * cal(a[i] - a[j], i) % P + f[i]) % P;

    cout << f[N];

    return 0;

}

巴特西

CSP202104-4 校门外的树

最新文章

热门文章