首先初始化状态f[0]=0,f[1]=1,f[2]=2;
然后使用递推来计算f[i]=(f[i-1]+f[i-2]);
唯一需要注意一点的是需要使用高精度
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = 5010;
int n;
vector<int> f[N];
vector<int> add(vector<int> a,vector<int> b)
{
int t=0;
vector<int> c;
for(int i=0;i<a.size()||i<b.size();i++)
{
if(i<a.size())t+=a[i];
if(i<b.size())t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t)c.push_back(t);
return c;
}
int main()
{
cin >> n;
f[0].push_back(0);
f[1].push_back(1);
f[2].push_back(2);
int c[40];
for(int i=3;i<=n;i++)
f[i]=add(f[i-2],f[i-1]);
for(int i=f[n].size()-1;i>=0;i--)cout << f[n][i];
return 0;
}
P2437 蜜蜂路线
通过图我们发现一个点只会与相邻的两个点有关系,因此这个题目类似于走楼梯的那一个题,只是初始化的位置不同而已
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = 5010;
int n,m;
vector<int> f[N];
vector<int> add(vector<int> a,vector<int> b)
{
int t=0;
vector<int> c;
for(int i=0;i<a.size()||i<b.size();i++)
{
if(i<a.size())t+=a[i];
if(i<b.size())t+=b[i];
c.push_back(t%10);
t/=10;
}
if(t)c.push_back(t);
return c;
}
int main()
{
cin >> n >> m;
f[n].push_back(0);
f[n+1].push_back(1);
f[n+2].push_back(2);
int c[40];
for(int i=n+3;i<=m;i++)
f[i]=add(f[i-2],f[i-1]);
for(int i=f[m].size()-1;i>=0;i--)cout << f[m][i];
return 0;
}
P1002 [NOIP2002 普及组] 过河卒
由于只能往下走或者向右走,因此这个题目类似于摘花生,所以状态转移为
f[i][j]=f[i-1][j]+f[i][j-1]
在此之前我们需要判断这个点是否可以被攻击到,因此需要预处理——用st[N][N]来判断当前的状态是否合法
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
马走日的小技巧
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
long long f[N][N];
int n,m,h1,h2;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool st[N][N];
int main()
{
cin >> n >> m >> h1 >> h2;
st[h1][h2]=true;
//预处理点
for(int i=0;i<8;i++)
{
int a=h1+dx[i],b=h2+dy[i];
if(a>=0&&a<=n&&b>=0&&b<=m)
st[a][b]=true;
}
//看每一行以及每一列的初始状态
for(int i=0;i<=n;i++)
if(!st[i][0])f[i][0]=1;
else break;
for(int i=0;i<=m;i++)
if(!st[0][i])f[0][i]=1;
else break;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!st[i][j])
f[i][j]=f[i-1][j]+f[i][j-1];
cout << f[n][m] << endl;
return 0;
}
P1164 小A点菜
典型的背包问题,别忘了初始化,初始化很重要
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N],n,m;
int w[N];
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> w[i];
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i-1][j-w[i]];
}
cout << f[n][m] << endl;
return 0;
}