HDU 2154 跳舞毯

r囧r小猫 2024-02-17 19:40 22阅读 0赞

由于长期缺乏运动，小黑发现自己的身材臃肿了许多，于是他想健身，更准确地说是减肥。  
小黑买来一块圆形的毯子，把它们分成三等分，分别标上A,B,C，称之为“跳舞毯”，他的运动方式是每次都从A开始跳，每次都可以任意跳到其他块，但最后必须跳回A，且不能原地跳.为达到减肥效果，小黑每天都会坚持跳n次，有天他突然想知道当他跳n次时共几种跳法，结果想了好几天没想出来－\_－  
现在就请你帮帮他，算出总共有多少跳法。  
![66450249571cb0bc1f3af12dacd11d95_v_1488852661][]

Input

测试输入包含若干测试用例。每个测试用例占一行，表示n的值(1<=n<=1000)。  
当n为0时输入结束。

Output

每个测试用例的输出占一行，由于跳法非常多，输出其对10000取模的结果.

Sample Input

2
    3
    4
    0

Sample Output

2
    2
    6

思路：dfs+记忆化搜索

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define mod 10000
    const int maxn=1000+2;
    int d[3][maxn];
    int n;
    int dfs(int i,int cur){
    	int &ans=d[i][cur];
    	if(ans)return ans; //当i块,cur层已经计算过了，就直接返回结果就行了，否则会超时（记忆化） 
    	if(cur==n){
    		if(i==0)
    		{
    			ans++;
    			ans%=mod;
    		}
    		return ans;
    	}
        
    	for(int j=0;j<3;j++){
    		if(i!=j)
    		{
    		ans+=dfs(j,cur+1);
    		ans%=mod;
    		}
    	}
    	return ans;	
    }
    int main(){
    	while(scanf("%d",&n)==1 && n){
    		memset(d,0,sizeof(d));
    		int ans=dfs(0,0);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[66450249571cb0bc1f3af12dacd11d95_v_1488852661]: https://odzkskevi.qnssl.com/66450249571cb0bc1f3af12dacd11d95?v=1488852661

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关抖音热门挑战：#跳舞翻车记

"跳舞翻车记"这应该是一个结合舞蹈和意外搞笑元素的抖音热门挑战。参与者通常会表演一些有创意、动作难度大但又容易出错的舞蹈，比如模仿经典电影桥段、走钢丝般的脚步等，然后在过程

心已赠人/ 2025年03月03日 20:24/ 0 赞/ 89 阅读

相关抖音热门挑战：#跳舞翻车记#

这个抖音热门挑战的名称非常有趣，它结合了舞蹈和一种意外或滑稽的情况。"跳舞翻车记"可能是指参与者在跳舞时因为各种原因摔倒或者出状况，这样的画面既展示了舞者的技巧，又带有喜剧效果

痛定思痛。/ 2025年02月10日 07:00/ 0 赞/ 136 阅读

相关抖音热门挑战：#跳舞翻车记#

这个挑战名称"跳舞翻车记"，看起来是一种结合舞蹈和喜剧元素的挑战。参与者需要在音乐节奏中展示自己的舞蹈技巧，同时要保持搞笑的一面，避免出现“翻车”的尴尬场面。这样的挑战通常

梦里梦外;/ 2025年01月04日 23:39/ 0 赞/ 142 阅读

相关【Kuangbin数论】阿拉丁和飞毯

[4577. 阿拉丁和飞毯 - AcWing题库][4577. _ - AcWing] 题意： ![ea349dd45bf947778b80c317e1c7f471.png

红太狼/ 2024年03月30日 13:39/ 0 赞/ 31 阅读

相关 HDU 2154 跳舞毯

由于长期缺乏运动，小黑发现自己的身材臃肿了许多，于是他想健身，更准确地说是减肥。小黑买来一块圆形的毯子，把它们分成三等分，分别标上A,B,C，称之为“跳舞毯”，他的运动方

r囧r小猫/ 2024年02月17日 19:40/ 0 赞/ 23 阅读

相关 A002-181-2154

文章目录一、关于需求分析与建模的读书心得 1) 我对需求分析与建模的认识与建议 1. 需求问题是当前软件开发面临的主要问题

港控/mmm°/ 2023年01月03日 01:46/ 0 赞/ 136 阅读

相关 Poj 2154 Color (Polya计数欧拉函数优化)

题意：给出两个整数n和p，代表一串项链有n个珠子，用n种颜色对其染色，有些颜色可以不用，求不同的项链数，结果模p。参考了：http://blog.csdn.net/wsni

深碍√TFBOYSˉ_/ 2022年09月17日 14:15/ 0 赞/ 230 阅读

相关 POJ 2154-Color（Polya定理-旋转串项链）

Color <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

爱被打了一巴掌/ 2022年06月17日 05:52/ 0 赞/ 315 阅读

相关我要跳舞

我要跳舞题记：看北京残奥会开幕式上北川折翼的小女孩起跳的芭蕾舞有感，谨以此文献给那位名叫李月的小女孩，祝愿她在人生的舞台上舞出曼妙的人生之舞！ ——代腾飞

朴灿烈づ我的快乐病毒、/ 2022年04月01日 12:28/ 0 赞/ 393 阅读

相关 UVA 10618 跳舞机（多阶段决策问题）

题意：有点复杂，据说紫书P291描述的题意有误，可以参考[https://www.cnblogs.com/sahdsg/p/10596948.html][https_www.

待我称王封你为后i/ 2021年12月14日 06:47/ 0 赞/ 154 阅读