【洛谷】P2437 蜜蜂路线

传送门

反思

• 简单dp+高精度
• dp确实很容易想到 但是高精度不熟悉就完蛋了
• 这里用二维数组模拟高进度 第1个是数字序号 第2个是个位十位百位模拟 res[i][j]
• ACCODE：

#include<bits/stdc++.h>
using namespace std;
//思路就是二维数组处理 高精度加法
int cnt;
int res[1003][1000];
int n,m;
int len;
void dfs(int x){for(int i=1;i<=len;i++){res[x][i]=res[x-1][i]+res[x-2][i];}for(int i=1;i<=len;i++){if(res[x][i]>9){res[x][i+1]+=res[x][i]/10;res[x][i]=res[x][i]%10;}}if(res[x][len+1]>0) len++;
}
int main(){cnt=0;cin>>m>>n;len=1;memset(res,0,sizeof(res));res[1][1]=1;res[2][1]=2;//从0开始for(int i=3;i<=n-m;i++) dfs(i);//这个是从某点到某点的结果 不一定是从1开始//求路径数量  然后从那个点开始 用长度衡量for(int i=len;i>0;i--){cout<<res[n-m][i];}cout<<endl;return 0;
}

坑：

这道题我一开始用的是for循环从1到n后来看了别人的解题 原来是从3开始到n-m的for循环 利用距离 而不是终点本身
这是因为题目要求的是路程种类 所以可以把起点m等同于1开始
然后看看长度是多少就好了
然后 我还有一个错点 就是 res[0][1]=0;res[1][1]=1;res[2][1]=2;
要自己虚构一个0起点