首页 > 代码库 > 【noi 2.6_9270】&【poj 2440】DNA(DP)
【noi 2.6_9270】&【poj 2440】DNA(DP)
题意:问长度为L的所有01串中,有多少个不包含"101"和"111"的串。
解法:f[i][j]表示长度为i的01串中,结尾2位的十进制数是j的合法串的个数。那么,便由f[i-1][ ]逐个推出。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define L (int)1e6+10 7 #define mod 2005 8 int f[L][6]; 9 10 int main() 11 { 12 int l; 13 scanf("%d",&l); 14 f[0][0]=f[0][4]=1,f[0][1]=f[0][2]=f[0][3]=0; 15 for (int i=1;i<=l;i++) 16 { 17 f[i][0]=(f[i-1][0]+f[i-1][2])%mod; 18 f[i][2]=(f[i-1][1]+f[i-1][3])%mod; 19 20 f[i][1]=f[i-1][0]; 21 f[i][3]=f[i-1][1]; 22 f[i][4]=(f[i][0]+f[i][1]+f[i][2]+f[i][3])%mod; 23 } 24 printf("%d\n",f[l][4]); 25 return 0; 26 }
优化:g[i]直接表示长度为i的01串中合法串的个数。由基本的二维式子逐层递推便可推出。
g[i]=f[i][0]+f[i][1]+f[i][2]+f[i][3]
f[i-1][]: =[0]*2+[1]*2+[2]+[3]
=g[i-1]+[0]+[1]
f[i-2][]: =[0]+[2]+[0]
f[i-3][]: =[0]+[2]+[1]+[3]+[0]+[2]
=g[i-3]+[0]+[2]
f[i-4][]: =[0]+[2]+[1]+[3]
=g[i-4]
即:g[i]=g[i-1]+g[i-3]+g[i-4];
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define L (int)1e6+10 7 #define mod 2005 8 int f[L]; 9 10 int main() 11 { 12 int l; 13 scanf("%d",&l); 14 f[1]=2,f[2]=4,f[3]=6,f[4]=9; 15 for (int i=5;i<=l;i++) 16 f[i]=(f[i-1]+f[i-3]+f[i-4])%mod; 17 printf("%d\n",f[l]); 18 return 0; 19 }
【noi 2.6_9270】&【poj 2440】DNA(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。