初学数位DP--hdu 2089

其实是做topcoder的时候碰到不会的题，看人家说要用数位dp，所以拿http://acm.hdu.edu.cn/showproblem.php?pid=2089来学习了一下

数位dp适合在一段数的区间内找出满足某些条件的数的个数，这个时候往往不能之间遍历，肯定会超时，则一般使用数位dp来解决

数位dp的常见形式是dp[i][j],表示开头是j的i位数满足条件的有多少个，当然也有其他dp[i][j][k]等等，但i,j,k都很小，不会像直接遍历那么耗时

像这道题的话，知道了dp[i][j]表示的是啥，就能列出状态转移方程（稍微认真看就能理解的）:

for(int i=1;i<=7;i++)

	{

		for(int j=0;j<10;j++)//枚举第i位可能出现的数

		{

			for(int k=0;k<10;k++)//枚举第i-1位可能出现的数

			{

				if(j!=4&&!(j==6&&k==2))

					dp[i][j]  += dp[i-1][k];

			}

		}

	}

更加具体的介绍可以参考：http://wenku.baidu.com/link?url=o3ER_gVCyB0qcKthM-Y8vPtAGZ_u5bzOu_gUCUhPcXC6YfaSDgtBSXNEEvvGvSzyuDE9TULcPNsDrRd9IUtQVHeKUVrnPUjyfWjCly_J7Xq

以下附上ac这题的代码：

#include <iostream>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

int dp[10][10];

void init()

{

	memset(dp,0,sizeof(dp));

	dp[0][0] = 1;

	for(int i=1;i<=7;i++)

	{

		for(int j=0;j<10;j++)//枚举第i位可能出现的数

		{

			for(int k=0;k<10;k++)//枚举第i-1位可能出现的数

			{

				if(j!=4&&!(j==6&&k==2))

					dp[i][j]  += dp[i-1][k];

			}

		}

	}

}

int solve(int n)

{

	init();

	int digit[10];

	int len = 0;

	while(n>0)

	{

		digit[++len] = n%10;

		n/=10;

	}

	digit[len+1]=0;

	int ans = 0;

	for(int i=len;i;i--)

	{

		for(int j=0;j<digit[i];j++)

		{

			if(j!=4&&!(digit[i+1]==6&&j==2))

				ans+=dp[i][j];

		}

		if(digit[i]==4||(digit[i]==2&&digit[i+1]==6))

			break;

	}

	return  ans;

}

int main()

{

	int l,r;

	while(cin>>l>>r)

	{

		if(l+r==0)

			break;

		else

			cout<<solve(r+1)-solve(l)<<endl;

	}

	return 0;

}

巴特西

初学数位DP--hdu 2089

最新文章

热门文章