SSL 2386 序列#线性动态规划#

2024-02-11 06:38

本文主要是介绍SSL 2386 序列#线性动态规划#,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛


题目

这里写图片描述
这里写图片描述


分析

dp,状态转移方程: f [ i ] [ j ] 表 示 第 j 位 的 数 字 是 i 的 方 案 f[i][j]表示第j位的数字是i的方案 f[i][j]ji
f [ i ] [ j ] + = f [ ( i 的 因 数 ) ] [ j − 1 ] ( 逆 推 ) f[i][j]+=f[(i的因数)][j-1](逆推) f[i][j]+=f[(i)][j1]
f [ i ∗ ( 1 t o n / j ) ] [ j ] + = f [ i ] [ j − 1 ] ( 顺 推 ) f[i*(1 _{to}n/j)][j]+=f[i][j-1](顺推) f[i(1ton/j)][j]+=f[i][j1]()


逆推代码

#include <cstdio>
#include <cstring>
using namespace std;
struct node{int x,y,next;}e[100001];
int f[2002][2002],n,m,k,ans,ls[2001];
int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) f[i][1]=1;for (int i=1;i<=n;i++)for (int j=1;j<=i;j++)if (i%j==0) e[++m].x=i,e[m].y=j,e[m].next=ls[e[m].x],ls[e[m].x]=m;//邻接表优化for (int j=2;j<=k;j++)for (int i=1;i<=n;i++){int t=ls[i];while (t){f[i][j]=(f[i][j]+f[e[t].y][j-1])%1000000007;t=e[t].next;}}for (int i=1;i<=n;i++) ans=(ans+f[i][k])%1000000007;printf("%d",ans);return 0;
} 

顺推代码

#include <cstdio>
#include <cstring>
#define p 1000000007
using namespace std;
int f[2002][2002],n,m,ans;
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) f[i][1]=1;for (int j=2;j<=m;j++)for (int i=1;i<=n;i++)for (int k=1;k<=n/i;k++) f[i*k][j]=(f[i][j-1]+f[i*k][j])%p;for (int i=1;i<=n;i++) ans=(ans+f[i][m])%p;printf("%d",ans);return 0;
} 

这篇关于SSL 2386 序列#线性动态规划#的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699093

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr