HDU3652 B-number

1420 단어 DP디지털 DP
제목: 숫자를 주고 이 수보다 작고 13이라는 자열을 포함하여 13으로 나누어진 수의 개수를 충족시키는 몇 개가 있느냐고 묻는다.
디지털 DP, 기억화 검색 실현, dp[i][j][k], i는 위치, j는mod13의 나머지 값, k는 3개의 값, 0은 13, 1은 13을 포함하지 않지만 현재 수는 3, 2는 13을 포함한다.
#include
#include
#include
using namespace std;
int dp[15][15][3];
int dig[15];
int dfs(int pos,int prenum,int premod,bool up,bool flag)	//up       ,flag     13
{
	if(pos<=0)
		return (flag&&premod==0);
	if(!up&&flag&&dp[pos][premod][0]!=-1)	//       13,          
		return dp[pos][premod][0];
	if(!up&&!flag&&prenum==1&&dp[pos][premod][1]!=-1)	//    1,       3  
		return dp[pos][premod][1];
	if(!up&&!flag&&prenum!=1&&dp[pos][premod][2]!=-1)	//     ,    13 
		return dp[pos][premod][2];
	int end=up?dig[pos]:9;
	int res=0;
	for(int i=0;i<=end;i++)
		res+=dfs(pos-1,i,(premod*10+i)%13,up&&(i==end),flag||(prenum==1&&i==3));
	if(!up)
	{
		if(!flag&&prenum==1)	
			dp[pos][premod][1]=res;
		if(!flag&&prenum!=1)
			dp[pos][premod][2]=res;
		if(flag)
			dp[pos][premod][0]=res;
	}
	return res;
}
int cal(int num)
{
	int k=0;
	while(num)
	{
		dig[++k]=num%10;
		num=num/10;
	}
	return dfs(k,0,0,1,0);
}
int main()
{
	int n;
	memset(dp,-1,sizeof(dp));
	while(scanf("%d",&n)==1)
	{
		printf("%d
",cal(n)); } return 0; }

좋은 웹페이지 즐겨찾기