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;
	}

• Re:我是用二分加数位DP做的，效果还行 (914) cnyali_lqz 2020-07-29 12:03:21