首页 > 代码库 > BZOJ2454 : TopCoder SRM 463 RabbitPuzzle
BZOJ2454 : TopCoder SRM 463 RabbitPuzzle
每种状态最多只有三种后继状态：中间往左跳，中间往右跳，两边往中间跳。
如果把它们分别看成左儿子、右儿子、父亲的话，那么会得到一些二叉树。
取出起始状态和终止状态往上跳$k$步的所有状态，其他状态我们只关心它们到关键状态的距离。
于是设$dp[i][j][k]$表示从起始状态跳了$i$步，目前位于状态$j$子树内距离$j$深度为$k$的状态的方案数，然后DP即可。
时间复杂度$O(k^3)$。
#include<cstdio>#include<algorithm>using namespace std;const int N=110,P=1000000007;struct E{ long long v[3]; void read(){ scanf("%lld%lld%lld",&v[0],&v[1],&v[2]); sort(v,v+3); } E left(){ E b; for(int i=0;i<3;i++)b.v[i]=v[i]; b.v[1]=b.v[0]*2-b.v[1]; swap(b.v[0],b.v[1]); return b; } E right(){ E b; for(int i=0;i<3;i++)b.v[i]=v[i]; b.v[1]=b.v[2]*2-b.v[1]; swap(b.v[1],b.v[2]); return b; } bool can(){ return v[0]+v[2]!=v[1]*2; } E up(){ E b; for(int i=0;i<3;i++)b.v[i]=v[i]; if(v[1]-v[0]<v[2]-v[1]){ b.v[0]=b.v[1]*2-b.v[0]; swap(b.v[0],b.v[1]); }else{ b.v[2]=b.v[1]*2-b.v[2]; swap(b.v[1],b.v[2]); } return b; } bool operator==(const E&b){return v[0]==b.v[0]&&v[1]==b.v[1]&&v[2]==b.v[2];}}S,T,now,a[N<<1];int K,n,i,j,k,t,son[N<<1][2],f[N<<1],dp[N][N<<1][N];inline void up(int&x,int y){x+=y;if(x>=P)x-=P;}inline int id(E b){ for(int i=1;i<=n;i++)if(a[i]==b)return i; return 0;}inline void push(E b){if(!id(b))a[++n]=b;}int main(){ S.read(); T.read(); scanf("%d",&K); for(push(now=S),i=1;i<=K;i++){ if(!now.can())break; push(now=now.up()); } for(push(now=T),i=1;i<=K;i++){ if(!now.can())break; push(now=now.up()); } for(i=1;i<=n;i++){ son[i][0]=id(a[i].left()); son[i][1]=id(a[i].right()); if(a[i].can())f[i]=id(a[i].up()); } dp[0][id(S)][0]=1; for(i=0;i<K;i++)for(j=1;j<=n;j++)for(k=0;k<=K;k++)if(dp[i][j][k]){ for(t=0;t<2;t++)if(k)up(dp[i+1][j][k+1],dp[i][j][k]); else{ if(son[j][t])up(dp[i+1][son[j][t]][0],dp[i][j][k]); else up(dp[i+1][j][1],dp[i][j][k]); } if(k)up(dp[i+1][j][k-1],dp[i][j][k]); else if(f[j])up(dp[i+1][f[j]][0],dp[i][j][k]); } return printf("%d",dp[K][id(T)][0]),0;}
BZOJ2454 : TopCoder SRM 463 RabbitPuzzle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。