Numere fără cifre vecine egale: digit DP în C++

Vrem să numărăm întregii din intervalul 0..N care nu au două cifre alăturate egale. Numărul 121 este acceptat, iar 122 nu este. Pentru N=20, singura valoare exclusă este 11, deci răspunsul este 20 din cele 21 de valori ale intervalului.

Ce înseamnă digit DP

Digit DP înseamnă programare dinamică pe cifre. În loc să încercăm toate numerele până la N, construim cifra cu cifra și grupăm prefixele care au aceleași informații relevante pentru continuare.

Citim N între 0 și 10^18, scris zecimal fără zerouri inițiale, cu excepția valorii 0. Afișăm numărul valorilor acceptate, incluzând zero. Citim limita ca text pentru a avea acces la cifrele ei; răspunsul rămâne numeric.

Trei informații despre un prefix

Starea dp[i][anterior][egal] numără prefixele de i poziții, cu ultima cifră reală anterior. Valoarea specială 10 spune că numărul nu a început încă, deoarece am ales numai zerouri inițiale. Indicatorul egal este 1 când prefixul coincide cu prefixul lui N și 0 când este deja mai mic.

Dacă suntem încă egali, următoarea cifră nu poate depăși cifra corespunzătoare din N. Dacă suntem deja mai mici, putem încerca 0..9. O cifră egală cu ultima cifră reală este respinsă.

Intervalul 0..20 conține 21 de întregi. Numai 11 are două cifre vecine egale, deci 20 de valori sunt acceptate.Mărește schema ↗

Varianta cu char[]

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    char s[20]; cin >> s;
    int n=static_cast<int>(strlen(s));
    long long dp[20][11][2]={}; dp[0][10][1]=1;
    for(int i=0;i<n;++i) for(int anterior=0;anterior<=10;++anterior)
        for(int egal=0;egal<=1;++egal) {
            int limita=egal?s[i]-'0':9;
            for(int cifra=0;cifra<=limita;++cifra) {
                if(anterior!=10 && cifra==anterior) continue;
                int urmator=(anterior==10 && cifra==0)?10:cifra;
                int ramaneEgal=egal && cifra==limita;
                dp[i+1][urmator][ramaneEgal]+=dp[i][anterior][egal];
            }
        }
    long long raspuns=0;
    for(int anterior=0;anterior<=10;++anterior)
        for(int egal=0;egal<=1;++egal) raspuns+=dp[n][anterior][egal];
    cout << raspuns << '\n';
}

Varianta echivalentă cu std::string

Păstrăm aceleași limite și exemple. Șirul clasic rezervă spațiu inclusiv pentru terminatorul nul; obiectul string își gestionează memoria. Indicii caracterelor utile pornesc de la zero în ambele variante.

#include <string>

#include <iostream>
#include <vector>
using namespace std;
int main() {
    string s; cin >> s;
    int n=static_cast<int>(s.size());
    vector<vector<vector<long long>>> dp(n+1,vector<vector<long long>>(11,vector<long long>(2))); dp[0][10][1]=1;
    for(int i=0;i<n;++i) for(int anterior=0;anterior<=10;++anterior)
        for(int egal=0;egal<=1;++egal) {
            int limita=egal?s[i]-'0':9;
            for(int cifra=0;cifra<=limita;++cifra) {
                if(anterior!=10 && cifra==anterior) continue;
                int urmator=(anterior==10 && cifra==0)?10:cifra;
                int ramaneEgal=egal && cifra==limita;
                dp[i+1][urmator][ramaneEgal]+=dp[i][anterior][egal];
            }
        }
    long long raspuns=0;
    for(int anterior=0;anterior<=10;++anterior)
        for(int egal=0;egal<=1;++egal) raspuns+=dp[n][anterior][egal];
    cout << raspuns << '\n';
}

Zerourile de completare nu sunt cifre ale numărului

Pentru limita 100, numărul 7 este reprezentat intern ca 007. Cele două zerouri inițiale nu trebuie să îl facă invalid. Cât timp anterior=10 și alegem zero, păstrăm valoarea 10. După prima cifră nenulă, zero devine o cifră obișnuită: în 100, ultimele două zerouri sunt reale și invalidează numărul.

Prefixul format numai din zerouri reprezintă o singură dată numărul 0, pe care îl acceptăm. Nu mai adăugăm separat încă o unitate la răspuns. Starea inițială are o singură posibilitate: niciun caracter ales și egalitate cu prefixul gol al limitei.

Pentru d cifre, timpul este O(d·11·2·10), iar memoria O(d·11·2). Limita are cel mult 19 cifre, deci tabloul clasic folosește 20 de niveluri, inclusiv cel inițial. Răspunsul este cel mult N+1 și încape în long long pentru domeniul declarat.

Exersează

Pentru N=0,9,10,11,20 și 100, răspunsurile sunt 1,10,11,11,20,91. Pentru limite mici, scrie separat un verificator care examinează toate numerele și compară numărările. Testul N=100 descoperă tratarea greșită a zerourilor inițiale.

Revezi cifrele unui număr, stările de programare dinamică și șirurile de caractere.

Întrebări frecvente

Ce înseamnă digit DP?

Digit DP este programare dinamică pe cifre. Construiește numerele cifră cu cifră și grupează prefixele după informațiile care influențează continuarea, evitând enumerarea tuturor valorilor până la N.

De ce trebuie memorată cifra precedentă?

Pentru a respinge alegerea aceleiași cifre pe poziția următoare. De exemplu, 121 este permis, dar 122 nu, deoarece ultimele două cifre sunt egale.

De ce tratez separat zerourile de la început în digit DP?

Ele pot fi doar completări ale reprezentării până la lungimea lui N, nu cifre reale ale numărului. Fără o stare care arată dacă numărul a început, ai putea respinge greșit numere mai scurte sau cazul zero.