程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3886 Final Kichiku “Lanlanshu” (數位dp)

hdu 3886 Final Kichiku “Lanlanshu” (數位dp)

編輯：C++入門知識

hdu 3886 Final Kichiku “Lanlanshu” (數位dp)

給出一個字符，只含'/'，'-' ，'' ，表示著一個數上的各位數字按相應字符上升，不變或下降，問【a,b】區間內這樣的數有多少個？

數組很好設，dp[i][j][k]表示處理到第i位，它對應的字符是第j位，它前面的數字是k的種類數。

令我糾結好久的是，我起初設的dp[i][j][k]表示處理到第i位時，它的上一位對應的字符是第j位，它的上一位數字是k的種類數，這樣可能會導致一個'/'只有一個數字，但是題目要求是'/'’-‘''必須是至少兩個相鄰的數字滿足。

如果把j理解為當前第i位應該對應的是第j個字符，那麼只需拿當前取的數字num和k相比是否滿足s[j]這種關系，若滿足，就繼續遞歸下一個字符，若不滿足，就拿num和k相比是否滿足s[j-1]關系，如果滿足，就繼續遞歸s[j]這種關系。

從這題可以得出結論，設置狀態的時候，要針對當前這一位，盡量讓當前這一位的選擇是確定的。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;
const int mod = 1e8;
char s[110],a[110],b[110],dig[110];
int slen,alen;
int dp[110][110][12];

bool check(int a, int b, char ch)
{
	if(ch == '/')
		return a < b;
	else if(ch == '-')
		return a == b;
	else
		return a > b;
}
int dfs(int len, int pos, int pre, int up, int first)
{
	if(len == alen)
	{
		return pos==slen;
	}
	if( !up && !first && dp[len][pos][pre] != -1 )
		return dp[len][pos][pre];
	int n = up ? (dig[len]-'0') : 9;
	int res = 0;
	for(int i = 0; i <= n; i++)
	{
		if(first)
			res += dfs(len+1,0,i,up&&i==n,first&&i==0);
		else
		{
			if( pos < slen && check(pre,i,s[pos]) ) 
				res += dfs(len+1,pos+1,i,up&&i==n,0);

			else if(pos > 0 && check(pre,i,s[pos-1]) )
				res += dfs(len+1,pos,i,up&&i==n,0);
		}
		res %= mod;
	}
	if(!up && !first)
		dp[len][pos][pre] = res;
	return res;
}
int cal(char x[], int f)
{
	memset(dp,-1,sizeof(dp));
	alen = strlen(x);
	int st = 0;
	while(x[st] == '0')
		st++;
	if(st >= alen)
		return 0;
	if(f == 1) //處理a-1
	{
		for(int i = alen-1; i >= st; i--)
		{
			if(x[i] >= '1')
			{
				x[i]--;
				break;
			}
			else
			{
				x[i] = '9';
			}
		}
	}
	strcpy(dig,x);
	return dfs(st,0,0,1,1);
}

int main()
{
	while(~scanf(%s,s))
	{
		slen = strlen(s);
		scanf(%s %s,a,b);
		printf(%08d
,((cal(b,0) - cal(a,1)%mod)+mod)%mod );
	}
	return 0;
}