[CCF 201312-4] 有趣的数 (数位DP) Apare_xzc

[CCF 201312-4] 有趣的数

---

题面

---

分析：

1. 一看就是数位DP

2. 这个数位DP只求满足条件的n位数的个数，所以比传统的规定了上下界的题目要简一点儿

3. 不让有前导零看似比较麻烦

4. 但是根据限制，0必须在1之前，2必须在3之前，于是我们可以得到这个有用的信息：首位一定是2。

5. 还规定0,1,2,3都要至少出现一次

6. 于是我们可以开几个变量记录数字0,1,2,3在高位是否出现过，命名为has0，has1,has2,has3

7. 令dp[pos][has0][has1][has2][has3]表示从0到最大的pos+1位数，前面出现了0,1,2,3对应的数的个数(瞎扯，自己理解好了)

8. 然后开心地记忆化搜索

---

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define LL long long 
LL dp[1050][2][2][2][2];
LL dfs(int pos,bool has0,bool has1,bool has2,bool has3,bool isFirst) 
{
	if(pos==-1)
	{
		if(has0&&has1&&has2&&has3) return 1;
		else return 0; 
	} 
	if(dp[pos][has0][has1][has2][has3]!=-1)
	{
		return dp[pos][has0][has1][has2][has3];
	}
	if(isFirst)
	{
		return dp[pos][has0][has1][has2][has3] = dfs(pos-1,has0,has1,true,has3,false);
	}
	LL ans = 0;
	//该位填0
	if(!has1)
	{
		ans = (ans+dfs(pos-1,true,has1,has2,has3,false))%mod;
	}
	
	//该位填1 
	if(has0)
	{
		ans = (ans+dfs(pos-1,has0,true,has2,has3,false))%mod;		
	} 
	
	//该位填2 
	if(!has3)
	{
		ans = (ans+dfs(pos-1,has0,has1,true,has3,false))%mod;
	}
	//该位填3 
	if(has2)
	{
		ans = (ans+dfs(pos-1,has0,has1,has2,true,false))%mod;
	}
	
	dp[pos][has0][has1][has2][has3] = ans;
	return ans;	
} 
LL solve(int n)
{
	if(n<=3) return 0;
	return dfs(n-1,false,false,false,false,true);
}

int main()
{
	int n;
	memset(dp,-1,sizeof(dp));	
	while(cin>>n) 
		printf("%lld\n",solve(n));
	
	return 0;
}

---

100分