BZOJ 1833 ZJOI 2010 count 數字計數 數位DP

BZOJ 1833 ZJOI 2010 count 數字計數 數位DP

題目大意：問0~9這10個數字在[l,r]中出現過多少次。

思路：數位DP。以前只是聽說過，並沒有寫過，寫了才發現好鬧心啊。。

預處理一個數組，f[i][j][k]表示長度為i，開頭為j，數字k出現的次數。

對於一個數kXXXXXX，我們先處理1~999999，然後處理1000000~kXXXXXX

前面的東西很規則，可以直接調用f數組來解決。

對於後面不太規則的東西，按位處理。總之就是亂搞，我也不太懂說不明白。。。

CODE：
 

#include 
#include 
#include 
#include 
using namespace std;

long long f[15][10][10],power[15];
long long a[10],b[10];

void Work(long long x,long long arr[])
{
	long long temp = x;
	int len = 0;
	static int digit[15];
	memset(digit,0,sizeof(digit));
	while(x)	digit[++len] = x % 10,x /= 10;
	x = temp;www.Bkjia.com
	for(int i = 1; i < len; ++i)
		for(int j = 1; j <= 9; ++j)
			for(int k = 0; k <= 9; ++k)
				arr[k] += f[i][j][k];
	for(int i = len; i; --i) {
		for(int j = 0; j < digit[i]; ++j) {
			if(!j && i == len)	continue;
			for(int k = 0; k <= 9; ++k)
				arr[k] += f[i][j][k];
		}
		arr[digit[i]] += x % power[i] + 1;
	}
}

int main()
{
	power[1] = 1;
	for(int i = 2; i <= 12; ++i)
		power[i] = power[i - 1] * 10;
	for(int i = 0; i <= 9; ++i)
		f[1][i][i] = 1;
	for(int i = 2; i <= 12; ++i)
		for(int j = 0; j <= 9; ++j)
			for(int k = 0; k <= 9; ++k) {
				for(int z = 0; z <= 9; ++z)
					f[i][k][z] += f[i - 1][j][z];
				f[i][k][k] += power[i - 1];
			}
	long long l,r;
	scanf("%lld%lld",&l,&r);
	Work(r,a),Work(l - 1,b);
	for(int i = 0 ; i <= 9; ++i)
		printf("%lld%c",a[i] - b[i]," \n"[i == 9]);
	return 0;
}