[TIOJ] 1021. G.Counting Page Numbers

題目連結:http://tioj.infor.org/problems/1021

---

這裡每個狀態存的是在這個狀態下有幾個k出現，而若現在再加一個k就是再加入前面數字的數量，所以我還先算了一下每個情況數字的數量。(我不太會數位DP，講的可能不是很好OAO

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int LogN = 10 + 5;

int dig[LogN], k, step;
lld cnt[LogN][2][2], dp[LogN][2][2];
int cnted[LogN][2][2], dped[LogN][2][2];

lld calc(int,bool,bool);
lld go(int,bool,bool);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n>>k){
		step++;
		int logN;
		for(logN = 0;n>0;logN++){
			dig[logN] = n%10;
			n/=10;
		}
		calc(logN, 0, 0);
		cout<<go(logN, 0, 0)<<'\n';
	}
	return 0;
}

lld calc(int pos, bool any, bool start){
	if(pos < 0){
		cnt[pos+1][any][start]=	start;
		return start;
	}
	if(cnted[pos+1][any][start] == step) return cnt[pos+1][any][start];
	cnted[pos+1][any][start] = step;
	auto& ret = cnt[pos+1][any][start];
	ret = 0;
	for(int i=0;i<10;i++){
		if(!any and i > dig[pos]) break;
		ret += calc(pos-1, any or i < dig[pos], start or i>0);
	}
	return ret;
}

lld go(int pos, bool any, bool start){
	if(pos < 0) return 0;
	if(dped[pos][any][start] == step) return dp[pos][any][start];
	dped[pos][any][start] = step;
	auto& ret= dp[pos][any][start];
	ret = 0;
	for(int i=0;i<10;i++){
		if(!any and i > dig[pos]) break;
		ret += go(pos-1, any or i < dig[pos], start or i > 0) + \
				(i==k)*cnt[pos][any or i < dig[pos]][start or i > 0]*(i!=0 or start);
	}
	return ret;
}