[TIOJ] 1021. G.Counting Page Numbers
題目連結:http://tioj.infor.org/problems/1021
這裡每個狀態存的是在這個狀態下有幾個k出現,而若現在再加一個k就是再加入前面數字的數量,所以我還先算了一下每個情況數字的數量。(我不太會數位DP,講的可能不是很好OAO
這裡每個狀態存的是在這個狀態下有幾個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;
}
留言
張貼留言