# Removing Digits II
https://cses.fi/problemset/task/2174
本篇文章參考：
https://abc864197532.github.io/2021/09/15/cses-additional-sol/
因為原文並沒有將細節及轉移式完整列出來，我想藉由本文章對其中的dp做較詳細的解釋，若有講解得不好，或是想要補充的可以聯絡我。
---
首先第一步，觀察的部分我借用作者的文章先混過去
簡單來說，要藉著將數字轉為x999...y，且可以用已知的步驟算出到(x-1)999...y，來解出這題
簡而言之，為完成上述工作，需要分成兩步驟
### 預處理
先設定dp[i][j][k]，i為9的個數，j為個位數，k為在那堆9之前的最大位元，這個state記錄著這個數字要變成(x-1)99999z需要的步數。
舉例來說：
x99999y會轉為 i = 5個9， j = y(0<=y<10)，k = maxdigit(x)
接著，設定to[i][j][k]，i、j、k與上面相同，to即是要那個z
此外，特別注意到當k=0的時候沒辦法消到<0，因此只會記錄到=0
下面為一些簡單的轉移式推導
| i j k | dp | to |備註|
| -------- | -------- | -------- |--- |
| 0 0 0 | 0 | 0 |0到0當然是0步|
| 0 1 0 |1 |0 | |
|依此類推 | | | |
|0 0 1 |1 |9 |9需要1步，尾數會變9|
|0 1 1 |2 |9 | |
|0 2 1 |2 |9 |根據這三個例子，可知只要k>j次數為1，else為2 |
|依此類推| | | |
將此轉為程式
```cpp=
if(i+j+k == 0){
to[i][j][k] = 0;
continue;
}
if(i+k == 0){
dp[i][j][k]=1,to[i][j][k]=0;
continue;
}
if(i == 0){
if(j < k)dp[i][j][k] = 1,to[i][j][k]=(10+j-k)%10;
else dp[i][j][k] = 2,to[i][j][k] = (10-k)%10;
continue;
}
```
1 0 0 這直觀的代表是"90"，這個數同時也可以看成xy，x為9，y為0，而中間9的數量為0。意謂他其實可以代表成0 0 9，這個數前面有記錄過了，因此，dp[1][0][0] += dp[0][0][9]，尾數改為to[0][0][9]。90這時便成了81，而81可以用前面的方法再繼續做。
90
81
73
66
54
49
36
27
18
09
00
這個部分可以用一個for迴圈解決
```cpp=
int last = j;
for(int l = 9; l >= 0; l--){
dp[i][j][k] += dp[i-1][last][l];
last = to[i-1][last][l];
}
to[i][j][k] = last;
```
接著到了1 0 1，與上面不同的是整個數列最少也會減掉k
舉個例子:190
190
181
173
166
154
149
136
127
118
109
100->99
可以發現最後還會多一步，若k換成其它值也會有同樣的狀況，所以程式碼稍作修改後長這樣
```cpp=
int last = j;
for(int l = 9; l >= 0; l--){
dp[i][j][k] += dp[i-1][last][max(k,l)];
last = to[i-1][last][max(k,l)];
}
to[i][j][k] = last;
```
### 處理n
做完預處理，接著是把輸入的值處理成可以用我們先算好得值。
假設有一數3234
根據剛剛預處理的經驗，可以聯想3234期可以表達成0 4 3。
接著ans += dp[0][4][3]。這時3234轉為"322?"，這個問號就是to[0][4][3]。
重複此步驟
3234 -> 322? -> 321? -> 320? -> 319? -> 309? -> 299? -> 199? -> 99? -> 0
理解其中的關係後就可以轉成程式碼了。
```cpp=
ll ans = 0;
while(n>0){
int i = numi(n);//numi找出9的個數
int k = maxdigital(n - n%(ll)pow(10,i+1));
//maxdigital找出x999...y中的x最大位元
int j = n%10;
ans += dp[i][j][k];
n -= (ll)pow(10,i+1);//x-1
n = n - n%10 + to[i][j][k];//將各位數換為to
}
```
最終程式碼
```cpp=
// __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define hutao_my_wife ios_base::sync_with_stdio(0);
#define forcalors_so_cute cin.tie(0);
#define ll long long
#define int ll //這個int單純是因為debug時懶得找溢位的程式碼
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define bug(A) cout<<A<<" hi\n";
using namespace std;
const int M = 200005;
ll dp[20][10][10];
ll to[20][10][10];
int maxdigital(ll x){
ll ans = 0;
while(x){
ans = max(ans,x%10);
x/=10;
}
return ans;
}
int numi(ll x){
x/=10;
int ans = 0;
while(x%10 == 9){
ans++;
x/=10;
}
return ans;
}
void solve(){
ll n;
cin>>n;
ll ans = 0;
while(n>0){
int i = numi(n);
int k = maxdigital(n - n%(ll)pow(10,i+1));
int j = n%10;
ans += dp[i][j][k];
n -= (ll)pow(10,i+1);
n = n - n%10 + to[i][j][k];
}
cout<<ans<<'\n';
}
signed main()
{
hutao_my_wife forcalors_so_cute
int t = 1;
memset(dp,0,sizeof(dp));
for(int i = 0; i <= 18; i++){
for(int k = 0; k < 10; k++){
for(int j = 0; j < 10; j++){
if(i+j+k == 0){
to[i][j][k] = 0;
continue;
}
if(i+k == 0){
dp[i][j][k]=1,to[i][j][k]=0;continue;
}
if(i == 0){
if(j < k)dp[i][j][k] = 1,to[i][j][k]=(10+j-k)%10;
else dp[i][j][k] = 2,to[i][j][k] = (10-k)%10;
continue;
}
int last = j;
for(int l = 9; l >= 0; l--){
dp[i][j][k] += dp[i-1][last][max(k,l)];
last = to[i-1][last][max(k,l)];
}
to[i][j][k] = last;
}
}
}
while(t--){
solve();
}
}
```
Sign in with Wallet
Connect another wallet