小团的装饰物

[编程题]小团的装饰物

热度指数：383 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团正在装饰自己的书桌，他的书桌上从左到右有m个空位需要放上装饰物。商店中每个整数价格的装饰物恰好有一种，且每种装饰物的数量无限多。

小团去商店的时候，想到了一个购买方案，他要让右边的装饰物价格是左边的倍数。用数学语言来说，假设小团的m个装饰物价格为 $a_1,a_2,...,a_m$ ，那么对于任意的1≤i≤j≤m， $a_j$ 是 $a_i$ 的倍数。

小团是一个节约的人，他希望最贵的装饰物不超过n元。现在，请你计算小团有多少种购买的方案？

输入描述:

输入包含两个数，n和m

输出描述:

输出一个数，结果对998244353取模，表示购买的方案数。

示例1

输入

4 2

输出

说明

[1,1][1,2][1,3][1,4][2,2][2,4][3,3][4,4]共8种

备注:

对于40%的数据，n,m≤10
对于100%的数据，1≤n,m≤1000

算法知识视频讲解

pein531

动态规划，dp[i][j]表示第i个物品房价格为j的装饰品时有多少种方案。当我们在确定第i个装饰物时，其实它的价格是有限制的，如果第i-1个装饰物价格为j，那么第i个装饰物的价格只能是j的整数倍，且不能超过n。而第i个装饰物对于任意确定的价格k=j*times，可能存在多组(j, times)乘积相同，把这些方案数全部加起来才能得到dp[i][k]，因此状态转移方程为：

dp[i][j*times] = dp[i][j*times] + dp[i - 1][j] times为整数，满足j*times<=n

最后将第m个装饰物的所有价格的方案数加起来就是我们要求的方案总数

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        // dp[i][j]表示第i个装饰物价格为j时的方案数
        int[][] dp = new int[m + 1][n + 1];
        // 第一个装饰物在价格确定时只有一种方案
        for(int j = 1; j <= n; j++)
            dp[1][j] = 1;
        for(int i = 2; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // 在n以内尝试各种倍数
                for(int times = 1; j*times <= n; times++){
                    dp[i][j*times] += dp[i - 1][j];
                    dp[i][j*times] %= 998244353;
                }
            }
        }
        int count = 0;
        // 第m个装饰物价格为1~n的所有方案都要加起来
        for(int j = 1; j <= n; j++) {
            count += dp[m][j];
            count %= 998244353;
        }
        System.out.println(count);
    }
}

发表于 2021-03-14 23:15:37 回复(0)

云云云一飞冲天

回溯只能过4个，后面都TLE了……ε=(´ο｀*)))😭

还得是看零葬大佬的dp解法😁

发表于 2022-09-09 14:50:22 回复(1)

Python

顺利上岸吧求求了

python运行超时，只过了四个。

利用动态规划

if __name__=='__main__':
    n,m=map(int, input().strip().split())
    dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
    res=0
    for j in range(n+1):
        dp[1][j]=1
    for i in range(2,m+1):
        for j in range(1,n+1):
            for time in range(1,n//j+1):
                dp[i][j*time]+=dp[i-1][j]
                dp[i][j*time]%=998244353
    for j in range(1,n+1):
        res+=dp[m][j]
        res%=998244353
    print(res)

发表于 2022-03-27 18:39:37 回复(0)

SuLi-97

#include<iostream>
using namespace std;
int main(){
    int n,m;
    cin >> n>>m;
    int dp[n+1][m+1];
    for(int i=1;i<=n;i++)
        dp[i][1] = n / i;
    for(int j=2;j<=m;j++){
        for(int i = 1;i<=n;i++){
            dp[i][j] = 0;
            int times = i;
            while(times <= n){
                dp[i][j] = (dp[i][j]+dp[times][j-1]) % 998244353;
                times += i;
            }
        }
    }
    cout<<dp[1][m];
}

发表于 2021-03-07 03:28:24 回复(0)

不偷不抢安度因_

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    const int mod = 998244353;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        dp[1][i] = 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k * j <= n; ++k) {
                dp[i + 1][j * k] = (dp[i][j] + dp[i + 1][j * k]) % mod;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = (res + dp[m][i]) % mod;
    }
    cout << res;
    return 0;
}

发表于 2021-03-03 14:52:42 回复(0)