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