题解 CF414B Mashmokh and ACM

ctq1999 · 2020-04-02 22:36:51 · 题解

题解

DP。

一个位置的状态肯定是由上一个位置的状态转移过来的。

设 f[i][j] 表示在 i 位置上填 j ，产生的最大方案数。

那么我们需要枚举当前位置，当前填的数字，上一个位置填的数字。

得出伪代码：

for (int i = 2; i <= k; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = j; k <= n; k++) {
            if (k % j == 0)
            f[i][k] = (f[i][k] + f[i - 1][j]) % mod;
        }
    }
}

时间复杂度 O(n^3) 。不能通过此题。

考虑优化。因为当前数应是前一个数的倍数，因为 k循环可以使用倍数 来减少循环。

for (int i = 2; i <= k; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k * j <= n; k++) {
            f[i][k * j] = (f[i][k * j] + f[i - 1][j]) % mod;
        }
    }
}

注意初始化。

时间复杂度 O(n^2) 。可以通过此题。

代码

#include <bits/stdc++.h>

#define MAXN 2010
#define mod 1000000007
#define ll long long

using namespace std;

int n, k;

ll f[MAXN][MAXN];

int main() {
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= n; i++) {
        f[1][i] = 1;
    }

    for (int i = 2; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k * j <= n; k++) {
                f[i][k * j] = (f[i][k * j] + f[i - 1][j]) % mod;
            }
        }
    }

    int sum = 0;
    for (int i = 1; i <= n; i++) sum = (sum + f[k][i]) % mod;
    cout << sum << endl;
    return 0;
}

日供一卒，功不唐捐。