hdu 4722 Good Numbers(dp)

題目鏈接：hdu 4722 Good Numbers

題目大意：給出a，b，問從a到b之間，有多少個好數字，好數字的定義為：每個位的數字相加是10的倍數。

解題思路：dp[i][j]表示第i位，前i-1位的和為j（j可以從200簡化成10，以為只需要考慮最後的數是否是10的倍數即可）有多少個數，需要注意的就是恰好為b的情況，所以要有一個跟蹤值s。

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int N = 20;

int c, t[N];
ll dp[N][N];

void cat (ll u) {
	c = 0;
	while (u) {
		t[c++] = u%10;
		u /= 10;
	}

	for (int i = 0; i < c/2; i++)
		swap(t[i], t[c-i-1]);
}

ll solve (ll u) {
	if (u < 0) return 0;
	else if (u == 0) return 1;

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

	cat(u);

	int s = 0;
	for (int i = 1; i <= c; i++) {

		for (int j = 0; j < 10; j++) {

			for (int k = 0; k < 10; k++)
				dp[i][(j+k)%10] += dp[i-1][j];
		}

		for (int k = 0; k < t[i-1]; k++)
			dp[i][(s+k)%10] += 1;
		s = (s + t[i-1]) % 10;
	}

	return dp[c][0] + (s == 0 ? 1 : 0);
}

int main () {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		ll a, b;
		cin >> a >> b;
		printf("Case #%d: ", i);
		cout <<	solve(b) - solve(a-1) << endl;
	}
	return 0;
}