首页 > 其他分享 >关于DP的一些模板与题目

关于DP的一些模板与题目

时间:2022-09-26 11:12:57浏览次数:61  
标签:maxx 题目 int long DP include 模板 1000

1.线性DP

  

斐波那契数列(%1000)实现

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long f[1000005],a[1000005];
long long DFS(int i)//斐波那契 
{
	if(i==1) return f[1]=1;
	if(i==2) return f[2]=1;
	if(f[i]>0) return f[i];
	return f[i]=(DFS(i-2)+DFS(i-1))%1000;
    //因为斐波那契这样的数列 是不断累加得到的结果
    //所以在每个结果后面%1000并不会影响最后得到%1000的结果
    //但如果只在最后写%1000 longlong也会炸
}
int main()
{
	int n;
	cin>>n;
	long long maxx=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxx=max(a[i],maxx);
	}
	DFS(maxx);

	for(int i=1;i<=n;i++)
		cout<<f[a[i]]<<endl; 
	
	return 0;
}
DP实现
 #include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long f[1000005],a[1000005];
int main()
{
	int n;
	cin>>n;
	f[1]=1,f[2]=1;
	for(int i=3;i<=n;i++)
		f[i]=f[i-1]+f[i-2];
	cout<<f[n];
	
	return 0;
}

标签:maxx,题目,int,long,DP,include,模板,1000
From: https://www.cnblogs.com/xdzxxintong/p/16730184.html

相关文章

  • Linux 中hdparm命令参数说明
    hdparm命令提供了一个命令行的接口用于读取和设置IDE或SCSI硬盘参数。语法hdparm(选项)(参数)选项-a:设定读取文件时,预先存入块区的分区数,若不加上选项,则显示目前的设定......
  • Linux 中hdparm命令使用说明——带实例
    详解Linux中hdparm命令查看硬盘信息的用法功能说明:显示与设定硬盘的参数。语法:hdparm[-CfghiIqtTvyYZ][-a][-A<0或1>][-c ][-d<0或1>][-k<0或1>][-K......
  • Highlight shopify主题模板配置修改
    Highlightshopify主题以创造性和吸引人的方式展示值得关注的产品,为较长的文本部分进行了优化,以支持品牌故事叙述,主题设置步骤简介,以允许快速启动,旨在展示形象,支持视觉品牌......
  • 拉格朗日插值优化 $dp$
    拉格朗日插值优化\(dp\)目录拉格朗日插值优化\(dp\)拉格朗日插值CF995FCowmpanyCowmpensation重要结论P4463calc拉格朗日插值对于一个\(n+1\)次多项式\(f(x)\),......
  • 【源码笔记】ThreadPoolExecutor#getTask
    /***Performsblockingortimedwaitforatask,dependingon*currentconfigurationsettings,orreturnsnullifthisworker*mustexitbecauseofanyo......
  • CF238E Meeting Her【DP,最短路】
    传送门显然,如果节点\(u\)不是\(s_i\tot_i\)的必经点,那么在\(u\)等\(i\)号车是没有前途的。类似地,若在\(u\)处上了\(i\)号车,且\(v\)不是\(s_i\tot_i\)......
  • MiniWord .NET Word模板引擎,藉由Word模板和数据简单、快速生成文件。
    Github/GiteeQQ群(1群):813100564/QQ群(2群):579033769视频教学介绍MiniWord.NETWord模板引擎,藉由Word模板和数据简单、快速生成文件。GettingStarted......
  • 【源码笔记】ThreadPoolExecutor#runWorker
    /***Mainworkerrunloop.Repeatedlygetstasksfromqueueand*executesthem,whilecopingwithanumberofissues:**1.Wemaystartoutwithanin......
  • WPF获取系统dpi
    WPF获取系统dpivardpiX=(int)typeof(SystemParameters).GetProperty("DpiX",BindingFlags.NonPublic|BindingFlags.Static).GetValue(null,null);vardpiY=(int......
  • 模板方法模式 Template Method
    “组件协作”模式:现代软件专业分工之后的第一个结果是“框架与应用程序的划分”,“组件协作”模式通过晚期绑定,来实现框架与应用程序之间的松耦合,是二者之间协作时常用的......