Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:我是用二分加数位DP做的,效果还行

Posted by cnyali_lqz at 2020-07-29 12:03:21 on Problem 3208
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator