大佬教程收集整理的这篇文章主要介绍了【题目】CF232C Doe Graphs，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
一看到题第一时间想到的大概是点的个数满足斐波那契数列的关系，即(fib_i=fib_{i-1}+fib_{i-2})，在题目中可以得知(fib_{0}=1,fib_{1}=2)（这里的(fib_{i})即为文中的(D_{i})）
然后考虑怎么求第n次的i到j的距离呢？自然想到这可能和上一次有关系，那么有什么关系呢？我们自然而然想到了递推（不习惯用f，这里用dp取代）
设(dp_{n,i,j})表示第n层，从i到j至少需要走的路径长度，然后考虑它怎么转移
下面分三种情况：
(,min(dp_{n-1,1,i}+dp_{n-1,j,fib_{n-1}}+2,dp_{n-1,i,fib_{n-1}}+dp_{n-1,1,j}+2)) //即经过新加的((1,fib_{n-1}+1))和((fib_{n-1},fib_{n-1}+1))的边
(+dp_{n-2,1,j-fib_{n-1}}+1) //即j点到1点的距离
若i,j相反则swap一下即可
(dp_{n,i,j}=dp_{n-2,i-fib_{n-1},j-fib_{n-1}})
此时处理好了dp，如果你这是以为大功告成了，那我告诉你你想简单了，想一想就知道这个dp有多庞大！！那肿么办呢？
通过观察发现这些式子中出现了很多很多个形如(dp_{n-1,1,x})和(dp_{n-1,x,fib_{m}})的式子，而且其它式子都可以通过这个得到！！
然后突然syx笑出了声，这不就直接处理一下就行了吗？！（然后笑着笑着就处理了一个晚上）
这怎么处理呢？咱又开始找规律了
因为对于每个询问，x是固定的，也就是说每层的dp值是固定的，那我们干脆把dp重新定义一下，(dp_{i,1/2,1/2})表示对于第i层图，当前是给定的两个点中的第一个点还是第二个点，是1到x的距离还是x到(fib_{n-1})的距离
我们发现对于两个点处理的方式都是一样的（因为只需要算1到x,x到(fib_{n-1})的距离），所以这里只讲一个了
我们先来看(dp_{i,1/2,1})
不难发现，这个特好处理
当(x≤fib_{n-1})时，(dp_{n,1,x}=min(dp_{n-1,1/2,1},dp_{n-1,1/2,2}+2)) 为什么呢？还是考虑此张图与上一张图的关系，从1到x就以为这1可以连到(fib_{n-1}+1)的节点上，然后再由(fib_{n-1}+1)的节点连到(fib_{n-1})的节点，那么你瞧瞧，你瞧瞧，从x到(fib_{n-1})的距离等于什么？等于(dp_{n-1,1/2,2}+2)啊！！于是再与直接不管第n层图新增的点相比较，就求出来了
当(x>fib_{n-1})时，就更好玩了，不就和之前讲到的一样，镜像一下，(dp_{n,1/2,1}=dp_{n-2,1/2,1}+1)
当(x≤fib_{n-1})时，(dp_{n,1/2,2}=min(dp_{n-1,1/2,1},dp_{n-1,1/2,2})+(n-1)/2+1) 这个玩意儿最重要的就是(n-1)/2+1的意思，此处希望读者先自行思考，然后看下一行
那么这个式子是什么意思呢？你考虑一下从第n层图中新增的第一个节点（即编号(fib_{n-1}+1)的节点）到最后一个节点的距离，它恰好是(n-1)/2（n=0或n=1时要特殊处理），然后再加上1到(fib_{n-1}+1)或者(fib_{n-1})到(fib_{n-1}+1)的一条边，距离一共是这么长
当(x>fib_{n-1})时，也是镜像一下，(dp_{n,1/2,2}=dp_{n-2,1/2,2})
于是你懂该怎么做了！！但是劝大家自己码一下，这题真的真的真的需要很锻炼细心，哪怕是先看一遍我的code再自己码也要码一遍
然后就开始代码大放送了！！
#include<bits/stdc++.h>
using namespace std;
#definE int long long
#define pb push_BACk
#define mk make_pair
#define fir first
#define sec second
inlinE int read() {
int x(0),neg(1);char ch(getchar());
while(!isdigit(ch)) {if (ch=='-') neg=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*neg;
}
const int MAXN=100;
int n,fib[85];
int dp[MAXN+5][2][2];
inline void DP_X(int tot,int X) {
if (tot==0) {
dp[tot][1][1]=dp[tot][1][2]=0;
}
else if (tot==1) {
if (x==1) dp[tot][1][1]=0; else dp[tot][1][1]=1;
if (x==2) dp[tot][1][2]=0; else dp[tot][1][2]=1;
}
else {
if (x<=fib[tot-1]) {
DP_X(tot-1,X);
dp[tot][1][1]=min(dp[tot-1][1][1],dp[tot-1][1][2]+2);
dp[tot][1][2]=min(dp[tot-1][1][1],dp[tot-1][1][2])+(tot-1)/2+1;
}
else {
DP_X(tot-2,x-fib[tot-1]);
dp[tot][1][1]=dp[tot-2][1][1]+1;
dp[tot][1][2]=dp[tot-2][1][2];
}
}
}
inline void DP_Y(int tot,int y) {
if (tot==0) {
dp[tot][2][1]=dp[tot][2][2]=0;
}
else if (tot==1) {
if (y==1) dp[tot][2][1]=0; else dp[tot][2][1]=1;
if (y==2) dp[tot][2][2]=0; else dp[tot][2][2]=1;
}
else {
if (y<=fib[tot-1]) {
DP_Y(tot-1,y);
dp[tot][2][1]=min(dp[tot-1][2][1],dp[tot-1][2][2]+2);
dp[tot][2][2]=min(dp[tot-1][2][1],dp[tot-1][2][2])+(tot-1)/2+1;
}
else {
DP_Y(tot-2,y-fib[tot-1]);
dp[tot][2][1]=dp[tot-2][2][1]+1;
dp[tot][2][2]=dp[tot-2][2][2];
}
}
}
inlinE int query(int tot,int x,int y) {
if (tot==0) return 0;
else if (tot==1) {
if (x==y) return 0;
return 1;
}
else if (x<=fib[tot-1]) {
if (y<=fib[tot-1]) {
return min(query(tot-1,x,y),min(dp[tot-1][1][1]+dp[tot-1][2][2],dp[tot-1][1][2]+dp[tot-1][2][1])+2);
}
else {
return min(dp[tot-1][1][1],dp[tot-1][1][2])+dp[tot-2][2][1]+1;
}
}
else {
return query(tot-2,x-fib[tot-1],y-fib[tot-1]);
}
}
signed main() {
int m=read(),n=read();
fib[0]=1;fib[1]=2;
n=min(n,78ll);
for (int i=2;i<=n;++i) fib[i]=fib[i-1]+fib[i-2];
for (int i=1;i<=m;++i) {
int x(read()),y(read());
memset(dp,0,sizeof(dp));
if (x>y) swap(x,y);
DP_X(n,X);DP_Y(n,y);
printf("%lldn",query(n,x,y));
}
puts("");
}
以上是大佬教程为你收集整理的【题目】CF232C Doe Graphs全部内容，希望文章能够帮你解决【题目】CF232C Doe Graphs所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。