首页 > 代码库 > [FJOI2007]轮状病毒
[FJOI2007]轮状病毒
题目描述
轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道，如图1。
n轮状病毒的产生规律是在n轮状基中删除若干边，使各原子之间有唯一一条信息通道。例如，共有16个不同的3轮状病毒，入图2所示。
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
输入输出格式
输入格式：第一行有1个正整数n。
输出格式：将编程计算出的不同的n轮状病毒数输出
输入输出样例
输入样例#1：
3
输出样例#1：
16
思路
根据。。。反正就是根据各种巨神遗产，天人感应，实践经验、、、得出递推式；
我用的是f[i]=f[i-1]*3-f[i-2]+2;
代码实现
1 #include<cstdio> 2 int n; 3 int f[110][300],l[110]; 4 int main(){ 5 f[1][0]=1,l[0]=l[1]=1; 6 scanf("%d",&n); 7 for(int i=2;i<=n;i++){ 8 f[i][0]+=2; 9 l[i]=l[i-1]+1;10 for(int j=0;j<l[i];j++){11 f[i][j]+=f[i-1][j]*3-f[i-2][j];12 if(f[i][j]<0){13 f[i][j]+=10;14 f[i][j+1]--;15 }16 f[i][j+1]+=f[i][j]/10;17 f[i][j]%=10;18 }19 while(!f[i][l[i]-1]) l[i]--;20 }21 for(int i=l[n]-1;i>=0;i--) printf("%d",f[n][i]);22 putchar(‘\n‘);23 return 0;24 }
[FJOI2007]轮状病毒
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。