首页 > 代码库 > hdu 2604 Queuing(dp递推)
hdu 2604 Queuing(dp递推)
昨晚搞的第二道矩阵快速幂，一开始我还想直接套个矩阵上去（原谅哥模板题做多了），后来看清楚题意后觉得有点像之前做的数位dp的水题，于是就用数位dp的方法去分析，推了好一会总算推出它的递推关系式了（还是菜鸟，对dp还是很不熟练）：
dp[i][0/1]表示以0/1开头的不含101且不含111的i位数（用1来表示f，0表示m，看着方便点），然后，状态转移方程是：
dp[i][0]=dp[i-1][0]+dp[i-1][1]; //以0开头的话后面接什么数都不成问题
dp[i][1]=dp[i-2][0]+dp[i-3][0];
在这里说下第二个，以1开头的话就要考虑多一些了，首先第i-2位一定不能是1，否则第i-1位取0/1都会构成101或111，所以第i位和第i-2位就确定了（即1x0xxx...）。接下来看第i-1位，如果取0的话，那么i-2位以后去什么数都没有问题，所以此时共有dp[i-2][0]种情况；如果取1的话，那么第i-3位就不能为1了，否则第i-1，i-2，i-3就会构成101，所以第i-3位只能取0，此时有dp[i-3][0]种情况，这就是第二个递推式子。
有了状态转移方程后，便很容易写出代码了，注意好边界的处理即可（因为涉及dp[i-3]的，所以前3个dp[i][0/1]都手算出来）：
1 #include<cstdio> 2 #include<cstring> 3 typedef long long LL; 4 int dp[1000006][2], mod; 5 //这个是线性递推的dp，4000+ms过的，不过也好开心了~ 6 7 inline void init(int n){ 8 dp[1][0]= dp[1][1]= 1%mod; 9 dp[2][0]= dp[2][1]= 2%mod;10 dp[3][0]= 4%mod; dp[3][1]= 2%mod;11 for(int i=4; i<=n; ++i){12 dp[i][0]= (dp[i-1][0]+dp[i-1][1])% mod;13 dp[i][1]= (dp[i-2][0]+dp[i-3][0])% mod;14 }15 }16 17 int main(){18 int L;19 while(~scanf("%d%d",&L,&mod)){20 init(L);21 printf("%d\n",(dp[L][0]+dp[L][1])%mod);22 }23 return 0;24 }
第一次提交后超时了，实际上是因为scanf函数少了个文件结束的标志，可我当时以为是算法的问题，又因为一开始就知道这道题是和矩阵快速幂有关的，所以只好构建矩阵来做了。把刚刚的递推关系整理了下：
dp[i][0]=dp[i-1][0]+dp[i-3][0]+dp[i-4][0]; //结合第2个式子可以得出的
dp[i][1]=dp[i-2][0]+dp[i-3][0];
所以有dp[i][0]=1*dp[i-1][0]+0*dp[i-2][0]+1*dp[i-3][0]+1*dp[i-4][0];
四阶的，系数分别为1,0,1,1，所以有 [dp[i],dp[i-1],dp[i-2],dp[i-3] ]T = A* [ dp[i-1],dp[i-2],dp[i-3],dp[i-4] ]T，其中矩阵 A =
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 int mod; 4 //在推出线性递推关系后构造矩阵来做，在一些细节问题上调试了好久， 5 //最后却因为scanf函数没写好返回超时 T.T，幸好最后幸运地发现了 6 //最后以500+ms过了，就不明白杭电上那些几十ms过的人究竟是怎么做的！ 7 8 struct matrix{ 9 int c[6][6],n;10 matrix(int n=0):n(n) { memset(c,0,sizeof(c)); }11 void identity(){12 for(int i=1; i<=n; ++i) c[i][i]= 1;13 }14 matrix operator *(const matrix &m2) const {15 matrix mul(n);16 for(int i=1; i<=n; ++i)17 for(int j=1; j<=n; ++j)18 for(int k=1; k<=n; ++k)19 mul.c[i][j]= (mul.c[i][j]+c[i][k]*m2.c[k][j]%mod)%mod;20 return mul;21 }22 } A(4);23 24 matrix quick_mod(matrix m, int b){25 matrix res(m.n);26 res.identity();27 while(b){28 if(b&1) res= res*m;29 m= m*m;30 b>>=1;31 }32 return res;33 }34 35 36 inline int dp_i0(int i){37 int dp[5]= {1,1,2,4,6};38 if(i<0) return 0;39 if(i<=4) return dp[i];40 matrix tmp= quick_mod(A,i-4);41 return (tmp.c[1][1]*dp[4]%mod +tmp.c[1][2]*dp[3]%mod +tmp.c[1][3]*dp[2]%mod +tmp.c[1][4]*dp[1]%mod)%mod;42 }43 44 int main()45 {46 A.c[1][1]= A.c[1][3]= A.c[1][4]= 1;47 A.c[2][1]= A.c[3][2]= A.c[4][3]= 1;48 int L;49 while(~scanf("%d%d",&L,&mod)){50 int ans[4]= {0,2,4,6};51 if(L<=3) { printf("%d\n",ans[L]%mod); continue ; }52 53 int dp_L0= dp_i0(L);54 int dp_L1= (dp_i0(L-2)+dp_i0(L-3))%mod;55 printf("%d\n",(dp_L0+dp_L1)%mod);56 }57 return 0;58 }
还是因为一些细节问题调试了好久，第一次提交后还是超时，无意中翻翻其他人的代码忽然看到那个scanf函数才猛然发觉自己的scanf函数没有文件结束的标志，改之，最后500+ms过了，果然logn的算法就是快啊~然后上面那个直接递推的代码也是同样的问题，改后提交也AC了，但却是4000+ms卡过的，看来后台数据应该是很多的，所以10^6的O(n)做法还是很接近时限的边缘……不过我还是不明白杭电上那些几十ms过的人到底是怎么做的！
hdu 2604 Queuing(dp递推)