Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我是用二分加数位DP做的,效果还行In Reply To:我是用二分加数位DP做的,效果还行 Posted by:ywz_l at 2014-04-29 22:27:11 > dp[i][0] 长度为i,首位连续0个6的个数 > dp[i][1] 长度为i,首位连续1个6的个数 > dp[i][2] 长度为i,首位连续2个6的个数 > dp[i][3] 长度为i, 符合的数有几个 > dp[0][0] = 1 > dp[i][0] = dp[i-1][0] * 9 + dp[i-1][1] * 9 + dp[i-1][2] * 9; > dp[i][1] = dp[i-1][0]; > dp[i][2] = dp[i-1][1] > dp[i][3] = dp[i-1][3] * 10 + dp[i-1][2]; > for (int i=len; i>=1;i--) > { > if (presix == 3) {ans = ans + trans(i);/*digit[i]digit[i-1]digit[k]digit[1];*/ break;} > if (digit[i]<=6) > ans = ans + digit[i] * dp[i-1][3]; > else if (presix == 0) > { > ans = ans + (digit[i]-1) * dp[i-1][3] + dp[i-1][2] + dp[i-1][3]; > } > else if (presix == 1) > { > ans = ans + (digit[i]-1) * dp[i-1][3] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]; > } > else if (presix == 2) > { > ans = ans + (digit[i]-1) * dp[i-1][3] + dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]; > } > if (digit[i] == 6) presix++; > else presix = 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator