HDU6831 : Fragrant numbers

[difficulty]

3.5/103.5/103.5/10
In fact, the very simple interval dp
But I didn't have time to think about it at that time//

[title]

Let SSS be an infinite string "1145141919" spliced together to become "114514191911451419114514191919..." "11451419114514191145141919 \ cdots" "11451419114514191145141911451419114514191145141919..."
Select a prefix TTT of SSS. You can insert '(') '+' * '(' \ quad ')'\quad '+'\quad '*' '(') '+' * '' ')' + '*' in TTT to form a new string T'T'T '
The value of val(T')val(T') val(T ') conforms to the general operation rules of decimal system
Now give you a number NNN, let you find the minimum length T, s.t.val(T ') = NT, s.t.\quad val(T')=NT, s.t.val(T ') = N
If there is no such string TTT, output - 1

[data range]

1≤N≤50001\le N\le 50001≤N≤5000

[sample input]

T
N

3
520
1
2

[sample output]

6
1
2

[interpretation]

When N=520:
T=114514,T′=1+1+4+514,val(T′)=520T=114514,T'=1+1+4+514,val(T')=520T=114514,T′=1+1+4+514,val(T′)=520

[ideas]

Generally, we can see that questions with a particularly small range of data can be processed by typing tables.
Since it is thought that the inner parentheses can be added arbitrarily, for two adjacent strings S[i,k] and S[k+1,j]S[i,k] and S[k+1,j]S[i,k] and S[k+1,j]
If S[i,k]S[i,k]S[i,k] can calculate the answer Vals [I, k] ∈ Aval_{S[i,k]}\in\mathbb{A}valS[i,k]​∈A
If S[k+1,j]S[k+1,j]S[k+1,j] can calculate the answer Vals [K + 1, J] ∈ Bval_{S[k+1,j]}\in\mathbb{B}valS[k+1,j]​∈B

So easy to get
S[i,j]={val∣val=p+qorval=p × Q   where p ∈ a   and   Q ∈ B}S[i,j]=\{val \mid val=p+q \quad or\quad val=p\times q \, where p\in\mathbb{A} \, and \, q\in \mathbb{B}\}S[i,j]={val ∣ Val = P + qorval = P × q. Where p ∈ A and Q ∈ B}

Other details:

Note that for an interval [i,j][i,j][i,j], there will be multiple different values, which are stored with set \ pmb{set} SetSet.
Note that when the number is greater than 5000, because there is no minus sign operation, the number will not become smaller, so do not insert it into the set

[preprocessing code]

Here NNN represents the length of the enumerated S array, not the NNN given by the title
Time complexity O (N3) × ∑∣S∣)O(n^3\times\sum|S|)O(n3 × ∑∣S∣)
I choose n=20n=20n=20 here. I can run it in one minute

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 20;			///In fact, just enumerate the S string with a length of 12 and open it slightly wider

set<int>S[MAX][MAX];			///set of interval DP
int fir[5050];				///Answer array
int tmp[MAX];    			///Stinky S array

void init(){
    for(int i=1;i<=5000;++i)fir[i]=INF;
    
    tmp[1]=tmp[2]=tmp[5]=tmp[7]=tmp[9]=1;
    tmp[3]=tmp[6]=4;
    tmp[4]=5;
    tmp[8]=tmp[10]=9;
    for(int i=11;i<MAX;++i)tmp[i] = tmp[i-10];      	///The stinky S array loops
    
    for(int L=1;L<=4;++L){				///First, deal with the value of interval S[i,j] without operator
        for(int i=1;i<MAX-L+1;++i){
            int j = i + L - 1;
            int t = 0;
            for(int k=i;k<=j;++k){
                t*=10;
                t+=tmp[k];
            }
            if(t>5000)continue;
            S[i][j].insert(t);
            if(i==1)fir[t]=min(fir[t],j);
        }
    }
}
int main(void){
    init();
    for(int L=2;L<MAX;++L){				///Interval DP enumeration interval length
        for(int i=1;i<MAX-L+1;++i){    			///Interval DP enumeration interval starting point
            int j = i + L - 1;				///Key points
            for(int k=i;k<j;++k){			///Enumerate the boundaries of two intervals
                for(auto &It_i : S[i][k]){
                    for(auto &It_j : S[k+1][j]){
                        int add = It_i + It_j;
                        int mul = It_i * It_j;
                        if(add<=5000){			///Pay attention to pruning
                            S[i][j].insert(add);
                            if(i==1)fir[add]=min(fir[add],j);	///Only i=1 is the prefix answer
                        }
                        if(mul<=5000){  		 ///Pay attention to pruning
                            S[i][j].insert(mul);
                            if(i==1)fir[mul]=min(fir[mul],j);
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=5000;++i){				///No solution should be output - 1. The output can be completed in the file
        printf("%d,",fir[i]==INF ? -1 : fir[i]);
    }
}