# [2020HDU multi calibration 6: interval dp] fragment numbers

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

T
N

3
520
1
2

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 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(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]);
}
}`

Posted by Nile on Wed, 25 May 2022 08:38:36 +0300